제출 #484717

#제출 시각아이디문제언어결과실행 시간메모리
484717kshitij_sodaniDojave (COCI17_dojave)C++14
126 / 140
2743 ms138760 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second #define endl '\n' llo it[1<<20]; llo ind[1<<20]; #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define ord tree<llo,null_type,less<llo>,rb_tree_tag,tree_order_statistics_node_update> vector<llo> re[1<<20]; vector<llo> le[1<<20]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); llo n; cin>>n; for(llo i=0;i<(1<<n);i++){ cin>>it[i]; ind[it[i]]=i; } if(n==1){ cout<<3<<endl; return 0; } llo xx2=(1<<n)-1; for(llo i=0;i<(1<<n);i++){ if((ind[i]<ind[i^xx2])){ // re[ind[i^xx2]].pb(ind[i]); le[ind[i]].pb(ind[i^xx2]); //cout<<ind[i]<<"<"<<ind[i^xx2]<<endl; } } llo ans=((xx2+1)*(xx2+2))/2; //cout<<ans<<endl; for(llo i=0;i<4;i++){ //start at mod i //end at (i+3)%4 llo jj=(i+3)%4; ord ss; multiset<llo> xx; for(llo j=(1<<n)-1;j>=0;j--){ for(auto ii:re[j]){ xx.insert(j); } if((j%4)==jj){ ss.insert(j); } for(auto ii:le[j]){ auto kk=xx.find(ii); xx.erase(kk); while(true){ auto ac=ss.lower_bound(j); if(ac==ss.end()){ break; } if((*ac)<ii){ ss.erase(ac); } else{ break; } } } if(j%4==i){ llo ec=(1<<n)+1; if(xx.size()){ ec=*(xx.begin()); } llo cot=ss.order_of_key(ec); /*if(cot>0){ cout<<j<<":"<<cot<<endl; for(auto jj:ss){ cout<<jj<<","; } cout<<endl; }*/ ans-=cot; } } } cout<<ans<<endl; return 0; }

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

dojave.cpp: In function 'int main()':
dojave.cpp:50:13: warning: unused variable 'ii' [-Wunused-variable]
   50 |    for(auto ii:re[j]){
      |             ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...