Submission #520045

#TimeUsernameProblemLanguageResultExecution timeMemory
520045nathanlee726Chameleon's Love (JOI20_chameleon)C++14
100 / 100
53 ms576 KiB
//#include<i_am_noob_orz> #include<bits/stdc++.h> #include "chameleon.h" #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long //#define int ll #define ull unsigned long long #define pii pair<int,int> #define X first #define Y second #define mod ((ll)1e9+7) #define pb push_back #define mp make_pair #define abs(x) ((x)>0?(x):(-(x))) #define F(n) Fi(i,n) #define Fi(i,n) Fl(i,0,n) #define Fl(i,l,n) for(int i=l;i<n;i++) #define memres(a) memset(a,0,sizeof(a)) #define all(a) a.begin(),a.end() #define sz(a) ((int)a.size()) #define ceiling(a,b) (((a)+(b)-1)/(b)) #define endl '\n' #define bit_count(x) __builtin_popcountll((x)) #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define jimmy_is_kind false typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree; //#define LOCAL #ifdef LOCAL #define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__) template<typename T> void _do(T && x) {cerr<<x<<endl;} template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);} #define IOS() #else #define IOS() ios_base::sync_with_stdio(0), cin.tie(0) #define endl '\n' #define bug(...) #endif int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);} int sub(int a,int b){return(a<b?a+mod-b:a-b);} int po(int a,int b){ if(b==0)return 1; if(b==1)return(a%mod); int tem=po(a,b/2); if(b&1)return(((tem*tem)%mod)*a)%mod; else return(tem*tem)%mod; } int GCD(int a,int b){ int x=0; int ra,rb; while(a&&b){ if(((a&1)==0)&&((b&1)==0)){ a>>=1,b>>=1,x++; } else if((a^b)&1){ if(a&1)b>>=1; else a>>=1; } else{ ra=abs(a-b),rb=min(a,b); a=ra,b=rb; } } return max(a,b)<<x; } int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);} #ifdef LOCAL int Query(vector<int> &v){for(int i:v)cout<<i<<" ";cout<<endl;return 0;} void Answer(int x,int y){} #endif int n,gr[1005]; bool vis[1005]; vector<int> g[1005],tv,rg[1005]; void dfs(int p,int ty){ vis[p]=1; gr[p]=ty; for(int u:g[p]){ if(!vis[u])dfs(u,1-ty); } } void fd_ed(int x){ Fi(ti,3){ if(sz(tv)==0)return; tv.pb(x+1); int re=Query(tv); int y; if(re!=sz(tv)){ //assert(re==sz(tv)-1); vector<int> ttv; F(sz(tv)-1)ttv.pb(tv[i]); while(sz(ttv)>1){ int mi=(sz(ttv)/2); vector<int> tttv; F(mi)tttv.pb(ttv[i]); tttv.pb(x+1); int re=Query(tttv); if(re!=sz(tttv)){ tttv.pop_back(); } else{ tttv.clear(); for(int i=mi;i<sz(ttv);i++)tttv.pb(ttv[i]); } swap(tttv,ttv); } assert(sz(ttv)==1); g[x].pb(ttv[0]-1); g[ttv[0]-1].pb(x); y=ttv[0]; } else{ return; } tv.pop_back(); vector<int> ttv; for(int i:tv){ if(i!=y)ttv.pb(i); } swap(tv,ttv); } } void Solve(int N){ n=N*2; F(n){ memres(vis); Fi(j,i){ if(!vis[j])dfs(j,0); } tv.clear(); Fi(j,i){ if(gr[j]==0)tv.pb(j+1); } if(sz(tv)!=0){ fd_ed(i); } tv.clear(); Fi(j,i){ if(gr[j]==1)tv.pb(j+1); } if(sz(tv)!=0){ fd_ed(i); } } F(n){ if(sz(g[i])==3){ vector<int> v1,v2; v1.pb(i+1);v1.pb(g[i][0]+1);v1.pb(g[i][1]+1); v2.pb(i+1);v2.pb(g[i][0]+1);v2.pb(g[i][2]+1); if(Query(v1)==1){ rg[i].pb(g[i][2]); rg[g[i][2]].pb(i); } else if(Query(v2)==1){ rg[i].pb({g[i][1]}); rg[g[i][1]].pb(i); } else{ rg[i].pb({g[i][0]}); rg[g[i][0]].pb(i); } } else assert(sz(g[i])==1); } memres(vis); F(n){ if(vis[i])continue; if(sz(g[i])==1){ Answer(i+1,g[i][0]+1); vis[i]=1; vis[g[i][0]]=1; continue; } if(g[i][0]!=rg[i][0]&&g[i][0]!=rg[i][1]){ Answer(i+1,g[i][0]+1); vis[i]=1; vis[g[i][0]]=1; } else if(g[i][1]!=rg[i][0]&&g[i][1]!=rg[i][1]){ Answer(i+1,g[i][1]+1); vis[i]=1; vis[g[i][1]]=1; } else{ Answer(i+1,g[i][2]+1); vis[i]=1; vis[g[i][2]]=1; } } } #ifdef LOCAL signed main(){ IOS(); Solve(10); return 0; } #endif
#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...