제출 #562987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562987		fcmalkcin	카멜레온의 사랑 (JOI20_chameleon)	C++17	100 / 100	78 ms	10028 KiB

chameleon

#include <bits/stdc++.h>
using namespace std;

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e5+10;
const ll mod=1e9+7  ;
const ll base=2e9;


/// i believe myself
/// goal 2/7

#include "chameleon.h"

/*ll Query(vector<ll> vt)
{
    for (auto to:vt) cout <<to<<" ";
    cout <<endl;
    ll x;
    cin>> x;
    return x;
}
void Answer(ll x,ll y)
{
    cout <<"! "<<x<<" "<<y<<endl;
}*/
ll par[maxn];
vector<ll> gr[maxn];

ll find_par(ll u)
{
    if (u==par[u]) return u;
    return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return ;
    if (gr[x].size()>gr[y].size()) swap(x,y);
    for (auto to:gr[x]) gr[y].pb(to);
    gr[x].clear();
    par[x]=y;
}
ll nxt[maxn];
bool dd[maxn];
vector<ll> adj[maxn];
void mer(ll x,ll y)
{
    adj[x].pb(y);
    adj[y].pb(x);
    dsu(x,nxt[y]);
    dsu(y,nxt[x]);
}
void dosth(vector<ll> vt,ll x)
{
    if (!vt.size()) return ;
    vector<ll> vt1=vt;
    vt1.pb(x);
    if (Query(vt1)!=(ll)vt1.size())
    {
        ll l=0, h=vt.size()-1;
        while (l<=h)
        {
            ll mid=(l+h)/2;
            vector<ll> vt1;
            for (int i=0;i<=mid;i++) vt1.pb(vt[i]);
            vt1.pb(x);
            if (Query(vt1)==(ll)vt1.size()) l=mid+1;
            else h=mid-1;
        }
        ll pos=l;
        mer(vt[pos],x);
        vector<ll> vt1;
        for (int i=pos+1;i<vt.size();i++) vt1.pb(vt[i]);
        dosth(vt1,x);
    }
}
bool chk(ll x,ll y)
{
  //  cout <<adj[x].size()<<" wtf1"<<endl;
    if (adj[x].size()==1)
    {
        return (adj[x][0]==y);
    }
    for (int i=0; i<3; i++)
    {
        if (adj[x][i]==y)
        {
            continue;
        }
        vector<ll> vt1;
        vt1.pb(x);
        vt1.pb(adj[x][i]);
        vt1.pb(y);
      //  cout <<x<<" "<<adj[x][i]<<" "<<adj[x].size()<<" "<<adj[y].size()<<" "<<y<<" wtf"<<endl;
        if (Query(vt1)==1)
            return true;
    }
    return false;
}
void Solve(ll n)
{
   n*=2;
   for (int i=1;i<=2*n;i++)
   {
       par[i]=i;
       if (i<=n)
       {
           nxt[i]=i+n;
           gr[i].pb(i);
       }
       else
       {
           nxt[i]=i-n;
       }
   }
   for (int i=2;i<=n;i++)
   {
       vector<ll> lf;
       vector<ll> rt;
       for (int j=1;j<=i-1;j++)
       {
           ll h=find_par(j);
           ll h1=find_par(nxt[j]);
           if (dd[h]||dd[h1]) continue;
           dd[h]=1;
           dd[h1]=1;
           for (auto to:gr[h]) lf.pb(to);
           for (auto to:gr[h1]) rt.pb(to);
       }
       for (int j=1;j<=i-1;j++) dd[find_par(j)]=false,dd[find_par(nxt[j])]=false;
       dosth(lf,i);
       dosth(rt,i);
   }
   for (int i=1;i<=n;i++)
   {
       if (dd[i]) continue;
       ll h=adj[i].size();
       assert((h==1||h==3));
       if (h==1)
       {
           ll x=adj[i][0];
           dd[i]=1;
           dd[x]=1;
           Answer(i,x);
       }
       else
       {
           bool chk1=false;
           for (int t=0;t<3;t++)
           {
               for (int t1=t+1;t1<3;t1++)
               {
                   vector<ll> vt;
                   vt.pb(i);
                   vt.pb(adj[i][t]);
                   vt.pb(adj[i][t1]);
                   if (Query(vt)==1)
                   {
                       chk1=true;
                       if (chk(adj[i][t],i))
                       {
                           dd[i]=1;
                           dd[adj[i][t]]=1;
                           Answer(adj[i][t],i);
                       }
                       else
                       {
                           dd[i]=1;
                           dd[adj[i][t1]]=1;
                           Answer(adj[i][t1],i);
                       }
                       break;
                   }
               }
               if (chk1) break;
           }
       }
   }
}


/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n;
    cin>>n;
    Solve(n);
}*/
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
*/
/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
*/

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'void dosth(std::vector<int>, int)':
chameleon.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int i=pos+1;i<vt.size();i++) vt1.pb(vt[i]);
      |                          ~^~~~~~~~~~

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