Submission #236607

#TimeUsernameProblemLanguageResultExecution timeMemory
236607LittleFlowers__Library (JOI18_library)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0); #define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a) #define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define mt make_tuple #define all(a) a.begin(),a.end() #define reset(f, x) memset(f, x, sizeof(f)) #define bit(x,i) ((x>>(i-1))&1) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1<<(i-1))) #define gg exit(0); //#define unx 1 #ifndef unx //#include "library.h" #endif // unx int n; int mode; vector<int> vast; #ifdef unx int a[1111]; void Answer(const vector<int>&q){ /** if(q.empty()){ cout<<0; gg } if(q[0]!=vast[0]) reverse(all(vast)); cout<<(q==vast); gg int has=0; forv(i,q) has|=!i; if(has || q.size()<n) cout<<0; else cout<<1; gg */ forv(i,q) cout<<i<<" "; gg } int Query(const vector<int>&q){ int has=0, tot=0; forinc(i,1,n){ if(q[a[i]-1]){ tot+=!has; has=1; } else has=0; } return tot; } #endif // unx int x[1111], y[1111], id[1111]; int root(int i){ return !id[i] ? i : id[i]=root(id[i]); } void join(int i,int j){ if((i=root(i))==(j=root(j))) return; id[i]=j; } int tim(const vector<int>&q,int mode=1){ vector<int> fac(n), ask(n); if(mode){ forv(i,q) fac[i-1]=1; forinc(i,1,n) if(fac[root(i)-1]) ask[i-1]=1; } else{ forv(i,q) ask[i-1]=1; } return Query(ask); } int dnc(vector<int> l,int i){ if(l.back()==i) l.pop_back(); if(l.size()<2) return l[0]; vector<int> r; while(l.size()>r.size()){ r.push_back(l.back()); l.pop_back(); } l.push_back(i); return tim(l) < l.size() ? dnc(l,i) : dnc(r,i); } int pf,sf; void dnc1(vector<int> l,int i,int has=2){ if(l.size()<2){ if(pf) sf=l[0]; else pf=l[0]; return; } vector<int> r; while(l.size()>r.size()){ r.push_back(l.back()); l.pop_back(); } if(mode){ //forv(t,l) cerr<<t<<" "; cerr<<":"<<has<<"\n"; //cerr<<(l.size()==to+1); //1 2 3 4 = 2 } l.push_back(i); int to=tim(l); if(l.size()==to+1){ l.pop_back(); dnc1(l,i,1); if(has>1) dnc1(r,i,1); } else if(l.size()==to){ dnc1(r,i,has); } else{ l.pop_back(); dnc1(l,i,has); } } vector<int> ad[1111]; void add(int i,int j){ ad[i].push_back(j); ad[j].push_back(i); } void Solve(int N){ n=N; vector<int> ask(n); ask[0]=x[1]=y[1]=1; vector<int> mp={1}; int tot=1; forinc(i,2,n){ ask[i-1]=1; int tmp=Query(ask); if(tot<tmp){ mp.push_back(i); x[i]=y[i]=i; } else if(tot>tmp){ //cerr<<i<<"\n"; pf=sf=0; if(i==4) mode=1; dnc1(mp,i); if(i==4){ //forv(j,mp) cerr<<j<<" "; //cerr<<pf<<" "<<sf; //gg } join(pf,i); join(sf,i); if(tim({x[pf],i},0)==1) add(x[pf],i), x[i]=y[pf]; else add(y[pf],i), y[i]=x[pf]; if(tim({x[sf],i},0)==1) add(x[sf],i), (x[i] ? y[i]=y[sf] : x[i]=y[sf]); else add(y[sf],i), (x[i] ? y[i]=x[sf] : x[i]=x[sf]); fordec(i,mp.size()-1,0){ if(mp[i]==pf || mp[i]==sf){ swap(mp[i],mp.back()); mp.pop_back(); } } mp.push_back(i); } else{ int to=dnc(mp,i); join(i,to); if(tim({x[to],i},0)==1){ add(i,x[to]); x[to]=i; } else{ add(i,y[to]); y[to]=i; } } //forv(j,mp) cerr<<j<<" "; cerr<<":"<<tmp<<"\n"; //cout<<"\n"; tot=tmp; } //forv(i,ad[10]) cerr<<i<<" "; //gg forinc(i,1,n){ if(ad[i].size()==1){ vector<int> ans(n); ans[0]=i; int pre=-1; forinc(j,2,n){ forv(t,ad[i]){ if(t!=pre){ ans[j-1]=t; pre=i; i=t; break; } } } vector<int> dup(n+1); forv(i,ans){ if(++dup[i]>1) exit(-1); } Answer(ans); gg } } } #ifdef unx main(){ #define task "library" freopen(task".inp","r",stdin); freopen(task".out","w",stdout); forinc(i,1,n=in) vast.push_back(a[i]=in); Solve(n); } #endif // unx

Compilation message (stderr)

library.cpp: In function 'int tim(const std::vector<int>&, int)':
library.cpp:86:12: error: 'Query' was not declared in this scope
     return Query(ask);
            ^~~~~
library.cpp: In function 'int dnc(std::vector<int>, int)':
library.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return tim(l) < l.size() ? dnc(l,i) : dnc(r,i);
            ~~~~~~~^~~~~~~~~~
library.cpp: In function 'void dnc1(std::vector<int>, int, int)':
library.cpp:124:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(l.size()==to+1){
        ~~~~~~~~^~~~~~
library.cpp:128:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     } else if(l.size()==to){
               ~~~~~~~~^~~~
library.cpp: In function 'void Solve(int)':
library.cpp:154:17: error: 'Query' was not declared in this scope
         int tmp=Query(ask);
                 ^~~~~
library.cpp:224:13: error: 'Answer' was not declared in this scope
             Answer(ans);
             ^~~~~~