Submission #937494

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

chameleon

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

namespace {

int n;

}  // namespace

void Solve(int N) {
    using namespace std;
    n=N;
    n*=2;
    /*vector<int> res(1<<n);
    for(int i=0;i<(1<<n);i++){
        vector<int> vec;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                vec.push_back(j+1);
            }
        }
        res[i]=Query(vec);
    }*/
    vector<vector<int>> one(n);
    vector<bool> two(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j==i) continue;
            if(Query({i+1,j+1})==1) one[i].push_back(j);
        }
        if((int)one[i].size()==1) two[i]=true;
        else{
            int a=one[i][0];
            int b=one[i][1];
            int c=one[i][2];
            if(Query({i+1,a+1,b+1})==1){
                one[i]={a,b};
            }
            else if(Query({i+1,b+1,c+1})==1){
                one[i]={b,c};
            }
            else if(Query({i+1,c+1,a+1})==1){
                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;
            }
        }
    }
    /*return ;
    for(int i=0;i<(1<<n);i++){
        vector<int> same(n);
        vector<int> prv(n,-1);
        for(int j=0;j<n;j++){
            if(two[j]) continue;
            if(i&(1<<j)){
                same[j]=1;
                prv[one[j][0]]=j;
            }
            else{
                same[j]=0;
                prv[one[j][1]]=j;
            }
        }
        bool tf=true;
        for(int j=0;j<n;j++){
            if(two[j]) continue;
            int x=prv[j];
            if(x==-1){
                tf=false;
                break;
            }
            int y=one[j][same[j]];
            if(y==-1){
                tf=false;
                break;
            }
            int ans=res[(1<<x)|(1<<j)|(1<<y)];
            if(ans!=1){
                tf=false;
                break;
            }
        }
        if(tf){
            vector<bool> used(n);
            for(int j=0;j<n;j++){
                if(used[j]) continue;
                int x=one[j][same[j]];
                assert(!used[x]);
                Answer(j+1,x+1);
                used[j]=used[x]=true;
            }
        }
    }*/
}

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