Submission #1318919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318919		wangzhiyi33	Mouse (info1cup19_mouse)	C++20	100 / 100	30 ms	332 KiB

mouse

#include <bits/stdc++.h>
#include "grader.h"

int query(vector<int> v);
int n;
mt19937 rnd(23232);
bool yey[300];


void solve(int N){
    n=N;
    vector<int>perm;
    for(int q=1;q<=n;q++){
        perm.push_back(q);
    }

    while(true){
        shuffle(perm.begin(),perm.end(),rnd);
        if(query(perm)==0)break;
    }
    // cout<<"PERM"<<endl;
    // for(auto x : perm){
    //     cout<<x<<" ";
    // }
    // cout<<endl;

    int benar=0,prv=0;
    while(true){
        vector<int>slh;
        for(int q=0;q<n;q++){
            if(!yey[q]){
                slh.push_back(q);
            }
        }
        if(slh.empty())break;
        vector<int>tmp;

        while(true){
            tmp=perm;
            shuffle(slh.begin(),slh.end(),rnd);
            for(int q=1;q<slh.size();q+=2){
                swap(tmp[slh[q-1]],tmp[slh[q]]);
            }

            int apa=query(tmp);
            if(apa==n)return;
            if(apa>prv)break;
        }

        // for(auto x : slh){
        //     cout<<x<<" ";
        // }
        // cout<<endl;

        int l=0,r=slh.size()/2;
        int brp=0;

        while(l<=r){
            int mid=(l+r)/2;
            tmp=perm;
            for(int q=0;q<mid;q++){
                swap(tmp[slh[2*q]],tmp[slh[2*q+1]]);
            }

            int apa=query(tmp);
            if(apa==n)return;
            if(apa>prv){
                brp=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }

        brp--;
        int a=slh[2*brp],b=slh[2*brp+1];
        
        swap(perm[a],perm[b]);
        int tot=query(perm);
        if(tot==n)return;

        if(tot-prv==2){
            yey[a]=yey[b]=true;
            benar=a;
            prv=tot;
            continue;
        }
        if(benar){
            tmp=perm;
            swap(tmp[a],tmp[benar]);
            int apa=query(tmp);
            if(apa==n)return;

            if(apa==tot-1){
                yey[b]=true;
            }
            else{
                yey[a]=true;
            }
            prv=tot;
        }
        else{
            int lain=1;
            while(lain==a || lain==b)lain++;

            tmp=perm;
            swap(tmp[lain],tmp[b]);
            int apa=query(tmp);
            if(apa==n)return;

            if(apa<tot){
                yey[b]=true;
                benar=b;
            }
            else{
                yey[a]=true;
                benar=a;
            }
            prv=tot;
        }
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49