Submission #562987

#TimeUsernameProblemLanguageResultExecution timeMemory
562987fcmalkcinChameleon's Love (JOI20_chameleon)C++17
100 / 100
78 ms10028 KiB
#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 */

Compilation message (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]);
      |                          ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...