Codeforces Round 988 (Div. 3)

C. Superultra's Favorite Permutation

打表出构造

#include<iostream>
using namespace std;
int n;
/**
 * #include<iostream>
using namespace std;

int n;
int a[100];bool vis[100];

bool isprime(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return 0;
    }
    return 1;
}
void dfs(int step){
    if(step==n+1){
        for(int i=1;i<=n-1;i++){
            if(isprime(a[i]+a[i+1]))return ;
        }
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }cout<<endl;
        return ;
    }

    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;a[step]=i;
            dfs(step+1);
            vis[i]=0;
        }
    }
}

int main(){
    for(int i=1;i<=5;i++){
        n=i;
        dfs(1);
    }
}
 */
int main(){
    int T;cin>>T;
    while(T--){
        cin>>n;
        if(n<=4){
            printf("-1\n");
        }else {
            //出5 4
           
                for(int i=1;i<=n;i+=2){
                    if(i==5)continue;
                    printf("%d ",i);
                }printf("5 4 ");
                for(int i=2;i<=n;i+=2){
                    if(i==4)continue;
                    printf("%d ",i);
                }printf("\n");
            
           
        }
    }
}

D. Sharky Surfing

#include<iostream>
using namespace std;
#include<queue>
#define ll long long
const ll N=200010;
ll n,m,L;
ll bl[N];ll br[N];
struct Node{
    ll x,v;
}node[N];
struct Compare {
bool operator()(ll a, ll b) {
return node[a].v< node[b].v; 
}
};

/**
 10

 */


int main(){
    ll T;cin>>T;
    while(T--){
        cin>>n>>m>>L;

        for(ll i=1;i<=n;i++){
            scanf("%lld%lld",&bl[i],&br[i]);
        }
        for(ll i=1;i<=m;i++){
            scanf("%lld%lld",&node[i].x,&node[i].v);
        }
        ll idx=1;priority_queue<ll,vector<ll>,Compare> pq;
        bool res=1;ll ans=0;ll now=1;
        for(ll i=1;i<=n;i++){

            //得到的是上个区间右
           while (idx<=m)
           {
            if(node[idx].x<bl[i]){
                pq.push(idx);idx++;
            }
            else break;
           }
           while(bl[i]<=node[idx].x&&node[idx].x<=br[i]){
            idx++;
           }
           //剩下的是落在区间右的

           
            while (1)
            {
                if(now>=br[i]-bl[i]+2)break;
                if(pq.empty()){
                    res=0;break;
                }
                ll t=pq.top();pq.pop();
                now+=node[t].v;ans++;
                if(now>=br[i]-bl[i]+2)break;
            }
        }
        if(!res){
            printf("-1\n");
        }else {
            printf("%lld\n",ans);
        }
    }
}

E. Kachina's Favorite Binary String

依次查询1到i，结果是不减的,cal[i]>=cal[i-1]
如果cal[i]>cal[i-1]比前面多了！只有这个是1，才能前面有多少0加多少个
如果cal[i]==cal[i-1]前面没有0，可能是1可能是0
前面有0，必然是0

这就可以分情况了，每一种情况仔细看

在没有获得第一个确定的由0变1时，
如果比前面多了！这个是由0变1，获得了由0变1
如果和前面一样，可能是0也可能是1
获得后，
如果比前面多，1
如果和前面一样，0，这每一位都可以确定
到最后都没有0变1，全都无法确定，可能是0000，111，111000

#include<iostream>
using namespace std;

const int N=10010;
int a[N];int n;int cal[N];
int pos=-1;

int main(){

    int T;cin>>T;
    while (T--)
    {
      cin>>n;
      for(int i=1;i<=n;i++)a[i]=-1;pos=-1;
      for(int i=2;i<=n;i++){
          printf("? 1 %d\n",i);fflush(stdout);
        scanf("%d",&cal[i]);
        if(pos==-1){
            if(cal[i]>cal[i-1]){
                int cnt0=cal[i]-cal[i-1];pos=i-1;
                for(int j=1;j<=i-1-cnt0+1;j++){
                    a[j]=1;
                }
                for(int j=i-1-cnt0+1;j<=i-1;j++){
                    a[j]=0;
                }a[i]=1;
            }else {

            }
        }else {
            if(cal[i]>cal[i-1]){
                a[i]=1;
            }else a[i]=0;
        }
      }
        if(pos==-1){
          //  cout<<"h2"<<endl;
            //全0或全1或11110000
            printf("! IMPOSSIBLE\n");fflush(stdout);
        }else {
                printf("! ");
                for(int i=1;i<=n;i++){
                    printf("%d",a[i]);
                }printf("\n");fflush(stdout);
        }
        
      }
}