Submission #944745

#TimeUsernameProblemLanguageResultExecution timeMemory
944745yeediotMinerals (JOI19_minerals)C++17
70 / 100
31 ms3596 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pb push_back #define sz(x) (int)(x.size()) #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) #define vi vector<int> #define vp vector<pii> #define vvi vector<vi> const int mxn=43000; #ifdef local void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);} set<int>cur; int color[mxn]; int cnt[mxn]; int n; bool ok; int tt=0; void init(){ cin>>n; for(int i=1;i<=2*n;i++){ cin>>color[i]; } } int res; int Query(int x){ tt++; if(cur.find(x)!=cur.end()){ cur.erase(x); cnt[color[x]]--; if(cnt[color[x]]==0)res--; } else{ cur.insert(x); cnt[color[x]]++; if(cnt[color[x]]==1)res++; } return res; } void Answer(int a,int b){ if(a>b)swap(a,b); cout<<a<<' '<<b<<'\n'; if(color[a]!=color[b]){ ok=0; } } #else void setio(){} #include "minerals.h" #endif ////////////////// vector<int>cur2; void Solve(int n){ vector<int>temp; int prev=0; for(int i=1;i<=2*n;i++){ if(Query(i)==prev+1){ prev++; temp.pb(i); } else{ cur2.pb(i); } } queue<tuple<vector<int>,int,int,bool>>Q; Q.push({temp,0,n-1,1}); while(sz(Q)){ auto [cur,l,r,flag2]=Q.front(); Q.pop(); if(l==r){ Answer(cur[0],cur2[l]); continue; } int mm=min(r-1,(l+r+5)/2); // int len=(r-l)*0.37; // if(flag2){ // mm=max(l,min(r-1,r-len)); // } // else{ // mm=min(r-1,max(l,l+len)); // } int dick; if(flag2){ for(int i=mm+1;i<=r;i++){ dick=Query(cur2[i]); } } else{ for(int i=l;i<=mm;i++){ dick=Query(cur2[i]); } } vector<int>L,R; for(auto i:cur){ int x=Query(i); if(x==dick){ L.pb(i); } else{ R.pb(i); } dick=x; } if(sz(L)){ Q.push({L,l,mm,1}); } if(sz(R)){ Q.push({R,mm+1,r,0}); } } } #ifdef local int main(){ ok=1; tt=0; setio(); init(); Solve(n); cout<<tt<<'\n'; if(ok)cout<<"Accepted!\n"; else cout<<"Wrong Answer\n"; } #else #endif /* input: 2n+nlogn+1/2(nlogn) */

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:101:13: warning: 'dick' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |             if(x==dick){
      |             ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...