Submission #1154963

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

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>
using namespace std;
/*const int MAXN=501;
int y[2*MAXN],c[2*MAXN],l[2*MAXN];
int cnt=0;
int Query(const vector<int> &p){
    map<int,int> mp;
    int n=p.size();
    int color[n];
    for(int i=0;i<n;i++){
        mp[p[i]]=1;
    }
    for(int i=0;i<n;i++){
        int x=p[i];
        if(mp.find(l[x])==mp.end()){
            color[i]=c[x];
        }
        else{
            color[i]=c[l[x]];
        }
    }
    mp.clear();
    for(int i=0;i<n;i++){
        mp[color[i]]=1;
    }
    return mp.size();
}
void Answer(int a,int b){
    assert(c[a]==c[b]);
    cnt++;
}*/
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){
                col[v]=0;
                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]={0};
    vector<vector<int>> nxt(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={u,graph[u][0],graph[u][1]};
        if(Query(temp)==1){
            nxt[u].push_back(graph[u][2]);
            nxt[graph[u][2]].push_back(u);
            continue;
        }
        temp={u,graph[u][0],graph[u][2]};
        if(Query(temp)==1){
            nxt[u].push_back(graph[u][1]);
            nxt[graph[u][1]].push_back(u);
            continue;
        }
        temp={u,graph[u][1],graph[u][2]};
        if(Query(temp)==1){
            nxt[u].push_back(graph[u][0]);
            nxt[graph[u][0]].push_back(u);
            continue;
        }
    }
    for(int u=1;u<=2*n;u++){
        if(gen[u]==0){
            map<int,int> mp;
            for(int v:nxt[u]){
                mp[v]=1;
            }
            for(int v:graph[u]){
                if(mp.find(v)==mp.end()){
                    gen[u]=v;
                    break;
                }
            }
        }
        if(u<gen[u]){
            Answer(u,gen[u]);
        }
    }
}
/*signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=2*n;i++){
        cin >> y[i];
    }
    for(int i=1;i<=2*n;i++){
        cin >> c[i];
    }
    for(int i=1;i<=2*n;i++){
        cin >> l[i];
    }
    Solve(n);
    assert(cnt==n);
}*/

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