Submission #1154956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154956		KhoaDuy	Chameleon's Love (JOI20_chameleon)	C++17	0 / 100	0 ms	440 KiB

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>
using namespace std;
/*int Query(const vector<int> &p){

}
void Answer(int a,int b){

}*/
vector<vector<int>> graph;
vector<int> col;
void DFS(int u){
    for(int v:graph[u]){
        if(col[v]==-1){
            col[v]=(col[u]^1);
            DFS(v);
        }
        else{
            assert(col[v]!=col[u]);
        }
    }
}
void Solve(int n){
    graph.clear();
    graph.resize(2*n+1);
    col.clear();
    col.resize(2*n+1);
    for(int u=2;u<=2*n;u++){
        for(int v=1;v<u;v++){
            col[v]=-1;
        }
        for(int v=1;v<u;v++){
            if(col[v]==-1){
                DFS(v);
            }
        }
        vector<int> v;
        for(int i=1;i<u;i++){
            if(col[i]==0){
                v.push_back(i);
            }
        }
        if(!v.empty()){
            v.push_back(u);
            while(Query(v)!=v.size()){
                int low=0,high=v.size()-2;
                while(low<high){
                    int mid=((high-low)>>1)+low;
                    vector<int> temp;
                    temp.push_back(u);
                    for(int i=0;i<=mid;i++){
                        temp.push_back(v[i]);
                    }
                    if(Query(temp)!=temp.size()){
                        high=mid;
                    }
                    else{
                        low=mid+1;
                    }
                }
                graph[u].push_back(v[high]);
                graph[v[high]].push_back(u);
                v.erase(v.begin()+high);
            }
        }
        v.clear();
        v.resize(0);
        for(int i=1;i<u;i++){
            if(col[i]==1){
                v.push_back(i);
            }
        }
        if(!v.empty()){
            v.push_back(u);
            while(Query(v)!=v.size()){
                int low=0,high=v.size()-2;
                while(low<high){
                    int mid=((high-low)>>1)+low;
                    vector<int> temp;
                    temp.push_back(u);
                    for(int i=0;i<=mid;i++){
                        temp.push_back(v[i]);
                    }
                    if(Query(temp)!=temp.size()){
                        high=mid;
                    }
                    else{
                        low=mid+1;
                    }
                }
                graph[u].push_back(v[high]);
                graph[v[high]].push_back(u);
                v.erase(v.begin()+high);
            }
        }
    }
    int gen[2*n+1];
    for(int u=1;u<=2*n;u++){
        if(graph[u].size()==1){
            gen[u]=graph[u][0];
            continue;
        }
        assert(graph[u].size()==3);
        vector<int> temp;
        temp={graph[u][0],graph[u][1]};
        if(Query(temp)==1){
            gen[u]=graph[u][2];
            continue;
        }
        temp={graph[u][0],graph[u][2]};
        if(Query(temp)==1){
            gen[u]=graph[u][2];
            continue;
        }
        temp={graph[u][1],graph[u][2]};
        if(Query(temp)==1){
            gen[u]=graph[u][0];
            continue;
        }
    }
    for(int u=1;u<=2*n;u++){
        if(u<gen[u]){
            Answer(u,gen[u]);
        }
    }
}
/*signed main(){

}*/

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