Submission #938221

#	Time	Username	Problem	Language	Result	Execution time	Memory
938221		guagua0407	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	54 ms	1032 KiB

chameleon

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

namespace {

using namespace std;
#define all(x) x.begin(),x.end()
map<vector<int>,int> mp;
int n;
mt19937 rng(time(NULL));

int query(vector<int> vec){
    for(auto &v:vec){
        v++;
    }
    int x=Query(vec);
    return x;
}

}  // namespace

void Solve(int N) {
    using namespace std;
    n=N;
    n*=2;
    vector<vector<int>> one(n);
    vector<bool> two(n);
    vector<int> B;
    for(int i=0;i<n;i++){
        B.push_back(i);
    }
    shuffle(all(B),rng);
    while(!B.empty()){
        vector<int> tmp;
        vector<int> A;
        for(auto v:B){
            int prv=(int)A.size();
            A.push_back(v);
            if(query(A)<=prv){
                A.pop_back();
                tmp.push_back(v);
            }
        }
        B=tmp;
        for(auto v:B){
            A.push_back(v);
            vector<int> del;
            while(query(A)!=(int)A.size()){
                A.pop_back();
                int l=0,r=(int)A.size()-1;
                while(l<r){
                    int mid=(l+r)/2;
                    vector<int> cur={v};
                    for(int i=0;i<=mid;i++){
                        cur.push_back(A[i]);
                    }
                    if(query(cur)!=(int)cur.size()){
                        r=mid;
                    }
                    else{
                        l=mid+1;
                    }
                }
                swap(A[l],A[(int)A.size()-1]);
                one[v].push_back(A.back());
                one[A.back()].push_back(v);
                //cout<<v+1<<' '<<A.back()+1<<'\n';
                del.push_back(A.back());
                A.pop_back();
                A.push_back(v);
            }
            A.pop_back();
            for(auto v:del){
                A.push_back(v);
            }
        }
    }
    for(int i=0;i<n;i++){
        if((int)one[i].size()!=1 and (int)one[i].size()!=3){
            cout<<-1<<'\n';
            return;
        }
        if((int)one[i].size()==1){
            two[i]=true;
            continue;
        }
        int a=one[i][0];
        int b=one[i][1];
        int c=one[i][2];
        if(query({i,a,b})==1){
            one[i]={a,b};
        }
        else if(query({i,b,c})==1){
            one[i]={b,c};
        }
        else{
            one[i]={c,a};
        }
    }
    vector<bool> used(n);
    for(int i=0;i<n;i++){
        if(used[i]) continue;
        if(two[i]){
            Answer(i+1,one[i][0]+1);
            used[i]=used[one[i][0]]=true;
            continue;
        }
        int a=one[i][0];
        int b=one[i][1];
        if(two[a]){
            Answer(i+1,a+1);
            used[i]=used[a]=true;
            continue;
        }
        else if(two[b]){
            Answer(i+1,b+1);
            used[i]=used[b]=true;
            continue;
        }
        else{
            if(one[a][0]==i or one[a][1]==i){
                Answer(i+1,a+1);
                used[i]=used[a]=true;
            }
            else{
                Answer(i+1,b+1);
                used[i]=used[b]=true;
            }
        }
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36