제출 #937551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937551		guagua0407	카멜레온의 사랑 (JOI20_chameleon)	C++17	0 / 100	35 ms	4784 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;
vector<int> cnt;
vector<bool> visited;
mt19937 rng(time(NULL));
int query(vector<int> vec){
    sort(vec.begin(),vec.end());
    if(mp.find(vec)!=mp.end()) return mp[vec];
    else{
        /*for(auto v:vec){
            cout<<v+1<<' ';
        }
        cout<<'\n';*/
        int x=Query(vec);
        mp[vec]=x;
        return x;
    }
}

void sir(vector<int> vec){
    sort(all(vec));
    if(mp.find(vec)==mp.end()){
        mp[vec]=-1;
    }
}

bool comp(int a,int b){
    return cnt[a]>cnt[b];
}

}  // 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);
    visited.resize(n);
    cnt.resize(n);
    for(int i=0;i<n;i++){
        vector<int> p(n);
        for(int j=0;j<n;j++){
            p[j]=j;
        }
        sort(all(p),comp);
        for(int k=0;k<n;k++){
            int j=p[k];
            if(j==i or j/(n/2)==i/(n/2)) continue;
            if(query({i+1,j+1})==1) one[i].push_back(j);
            if((int)one[i].size()==3) break;
        }
        for(int j=0;j<n;j++){
            if(j==i) continue;
            sir({i,j});
            if(query({i,j})!=1) cnt[j]++;
        }
        if((int)one[i].size()==1){
            two[i]=true;
            visited[one[i][0]]=true;
        }
    }
    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];
        int c=one[i][2];
        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(two[c]){
            Answer(i+1,c+1);
            used[i]=used[c]=true;
            continue;
        }
        else{
            if(one[a][0]==i or one[a][1]==i){
                Answer(i+1,a+1);
                used[i]=used[a]=true;
            }
            if(one[b][0]==i or one[b][1]==i){
                Answer(i+1,b+1);
                used[i]=used[b]=true;
            }
            else{
                Answer(i+1,c+1);
                used[i]=used[c]=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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36