Submission #58452

#TimeUsernameProblemLanguageResultExecution timeMemory
58452kingpig9Last supper (IOI12_supper)C++11
0 / 100
306 ms30872 KiB
#include <bits/stdc++.h> #include "advisor.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; static const int MAXN = 1e5 + 10; //#define debug(...) fprintf(stderr, __VA_ARGS__) #define debug(...) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) #warning static (advisor) static int *C, N, K, M; static set<pii> st; //pii(when we neet i, i) -- you remove GREATEST of them. static bool has[MAXN]; static vector<int> inds[MAXN]; static vector<int> getans() { //let's just implement -- get the bits //+ 10 just for the adjustment. Makes no difference for max values of N, K. for (int i = 0; i < N; i++) { inds[i].push_back(N); } for (int i = N - 1; i >= 0; i--) { inds[C[i]].push_back(i); } for (int i = 0; i < K; i++) { has[i] = true; st.emplace(inds[i].back(), i); } vector<int> ans; for (int i = 0; i < N; i++) { if (has[C[i]]) { st.erase(pii(inds[C[i]].back(), C[i])); inds[C[i]].pop_back(); st.insert(pii(inds[C[i]].back(), C[i])); ans.push_back(N); //this is bad debug("Bad\n"); continue; } //remove one inds[C[i]].pop_back(); auto it = --st.end(); pii tp = *it; st.erase(it); has[tp.se] = false; debug("tp.se = %d\n", tp.se); ans.push_back(tp.se); st.insert(pii(inds[C[i]].back(), C[i])); //add C[i] has[C[i]] = true; } return ans; } static void go() { //if < 25000 vector<int> ans = getans(); vector<int> lastind(N + 1, N); for (int i = 0; i < N; i++) { debug("ans[%d] = %d\n", i, ans[i]); lastind[C[i]] = i; } for (int i = 0; i < N; i++) { debug("lastind[%d] = %d\n", i, lastind[i]); } //will it be taken for (int i = 0; i < K; i++) { debug("i = %d. Advice = %d\n", i, lastind[i] == N); WriteAdvice(lastind[i] == N); } for (int i = 0; i < N; i++) { debug("ans[%d] = %d. advice = %d\n", i, ans[i], lastind[ans[i]] == i); WriteAdvice(lastind[ans[i]] == i); } } void ComputeAdvice (int *ccc, int nnn, int kkk, int mmm) { C = ccc; N = nnn; K = kkk; M = mmm; go(); }
#include <bits/stdc++.h> #include "assistant.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; static const int MAXN = 1e5 + 10; #define debug(...) fprintf(stderr, __VA_ARGS__) //#define debug(...) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) #warning static (assistant) static unsigned char *A; static int N, K; static int cur[MAXN]; static bool has[MAXN]; static void go() { priority_queue<pii> pq; for (int i = 0; i < K; i++) { cur[i] = i; has[i] = true; pq.emplace(A[i], i); } A += K; for (int i = 0; i < N; i++) { //replace it with this int req = GetRequest(); if (has[req]) { continue; } int ind = pq.top().se; int &ref = cur[ind]; //debug("REF %d\n", ref); PutBack(ref); has[ref] = false; pq.pop(); ref = req; pq.emplace(A[i], ind); has[req] = true; } } void Assist (unsigned char *aaa, int nnn, int kkk, int rrr) { A = aaa; N = nnn; K = kkk; go(); }

Compilation message (stderr)

advisor.cpp:17:2: warning: #warning static (advisor) [-Wcpp]
 #warning static (advisor)
  ^~~~~~~

assistant.cpp:17:2: warning: #warning static (assistant) [-Wcpp]
 #warning static (assistant)
  ^~~~~~~
#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...