제출 #1175326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175326		betvoi	카멜레온의 사랑 (JOI20_chameleon)	C++20	100 / 100	36 ms	532 KiB

chameleon

#include <bits/stdc++.h>
#include "chameleon.h"
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

int n,l[1000],xr[1002],qr=0;
int cm[1000],cl[1002];
bool c[1000],c1[1000],cnt[1002];
vector<int> g[1002],cur1,cur;
queue<int> qu;
void bfs(int x) {
    while(sz(qu)) qu.pop();
    cl[x]=0;
    qu.push(x);
    while(sz(qu)) {
        int u=qu.front();
        qu.pop();
        for(auto v: g[u])
            if (cl[v]==-1) {
                cl[v]=!cl[u];
                qu.push(v);
            }
    }
}
void add(int u) {
    if (cur1.empty()) return;
    vector<int> tmp;
    tmp=cur1;
    tmp.pb(u);
    if (Query(tmp)>=sz(tmp)) return;
    int j=0;
    tmp.clear();
    while(j<sz(cur1)) {
        tmp.clear();
        For(i,j,sz(cur1)-1) tmp.pb(cur1[i]);
        tmp.pb(u);
        if (j>=sz(cur1) || Query(tmp)>=sz(tmp)) return;
        int l=j,r=sz(cur1)-1;
        while(l<r) {
            int mid=l+(r-l)/2;
            tmp.clear();
            For(i,j,mid) tmp.pb(cur1[i]);
            tmp.pb(u);
            if (Query(tmp)<sz(tmp)) r=mid;
            else l=mid+1;
        }
        g[u].pb(cur1[l]);
        g[cur1[l]].pb(u);
        j=l+1;
    }
}
void Solve(int N) {
    n=N;
    For(i,1,n*2) g[i].clear();
    For(i,1,n*2) {
        for(auto el: cur) cl[el]=-1;
        for(auto el: cur)
            if (cl[el]==-1) bfs(el);
        cur1.clear();
        for(auto el: cur)
            if (cl[el]) cur1.pb(el);
        add(i);
        cur1.clear();
        for(auto el: cur)
            if (!cl[el]) cur1.pb(el);
        add(i);
        cur.pb(i);
    }
    // For(i,1,n*2) {
    //     cout << i << endl;
    //     for(auto el: g[i]) cout << el << " ";
    //     cout << endl; 
    // }
    vector<int> tmp;
    For(i,1,n*2) 
        if (sz(g[i])==3) {
            tmp.clear();
            tmp.pb(i),tmp.pb(g[i][0]),tmp.pb(g[i][1]);
            if (Query(tmp)==1) xr[i]=g[i][2];
            else {
                tmp.pop_back();
                tmp.pb(g[i][2]);
                if (Query(tmp)==1) xr[i]=g[i][1];
                else xr[i]=g[i][0];
            }
        }
    For(i,1,n*2) {
        if (cnt[i]) continue;
        if (sz(g[i])==1) {
            cnt[i]=cnt[g[i][0]]=1;
            Answer(i,g[i][0]);
        } else {
            for(auto el: g[i]) {
                if (el!=xr[i] && ((sz(g[el])==1 && g[el][0]==i) || (sz(g[el])==3 && xr[el]!=i))) {
                    Answer(el,i);
                    cnt[el]=cnt[i]=1;
                    break;
                }
            }
        }
    }
}

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