Submission #1038274

#TimeUsernameProblemLanguageResultExecution timeMemory
1038274idasLast supper (IOI12_supper)C++11
43 / 100
107 ms6480 KiB
#include <bits/stdc++.h> #include "advisor.h" #define FOR(i, begin, end) for(int i=(begin); i<(end); i++) #define s second #define f first using namespace std; typedef pair<int, int> pii; namespace advisor{ const int MxN=1e5+10, INF=1e9; int n, k, c[MxN], nxt[MxN], cur[MxN]; unsigned char bits[MxN]; } using namespace advisor; void ComputeAdvice(int *C, int N, int K, int M) { n=N; k=K; FOR(i, 0, n) c[i]=C[i], cur[i]=INF; for(int i=n-1; i>=0; i--){ nxt[i+k]=cur[c[i]]; cur[c[i]]=i; } FOR(i, 0, k) nxt[i]=cur[i]; FOR(i, 0, n+k) bits[i]=0; set<pii> cols; set<pii, greater<pii>> st; FOR(i, 0, k) st.insert({nxt[i],i}), cols.insert({i,i}); FOR(i, 0, n) { auto src=cols.lower_bound({c[i],0}); if(src!=cols.end() && (*src).f==c[i]){ auto it=src; int in=(*it).s; st.erase({nxt[in],in}); cols.erase(it); cols.insert({c[i],i+k}); st.insert({nxt[i+k],i+k}); } else{ auto it=st.begin(); int in=(*it).s; bits[in]=1; // cout << "rem: " << in << endl; st.erase(it); int col; if(in<k) col=in; else col=c[in-k]; cols.erase({col,in}); cols.insert({c[i],i+k}); st.insert({nxt[i+k],i+k}); } } FOR(i, 0, n+k) WriteAdvice(bits[i]); // FOR(i, 0, n+k) cout << int(bits[i]); // cout << endl; }
#include <bits/stdc++.h> #include "assistant.h" #define FOR(i, begin, end) for(int i=(begin); i<(end); i++) #define pb push_back #define s second #define f first using namespace std; typedef vector<int> vi; void Assist(unsigned char *bits, int n, int k, int r) { vi bad; set<int> cols; FOR(i, 0, k) { cols.insert(i); if(bits[i]==1) bad.pb(i); } // FOR(i, 0, n+k) cout << bits[i]; // cout << endl; // cout << "bad: "; // for(auto it : bad) cout << it << " "; // cout << endl; FOR(i, k, n+k) { int next_col=GetRequest(); if(!cols.count(next_col)){ cols.erase(bad.back()); PutBack(bad.back()); bad.pop_back(); } if(bits[i]==1) bad.pb(next_col); cols.insert(next_col); } }
#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...