Submission #57066

#TimeUsernameProblemLanguageResultExecution timeMemory
57066kingpig9Last supper (IOI12_supper)C++11
34 / 100
641 ms47864 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 subtask; static int *C, N, K, M; static int logn, logk; 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 send (int x, int largestbit) { debug("x = %d. ADVICE: ", x); for (int i = largestbit; i >= 0; i--) { WriteAdvice((x >> i) & 1); debug("%d", (x >> i) & 1); } debug("\n"); } namespace advisor_subtask3 { int where[MAXN]; int cur[MAXN]; void go() { //if < 25000 vector<int> ans = getans(); for (int i = 0; i < K; i++) { where[i] = i; cur[i] = i; } for (int i = 0; i < N; i++) { int x = ans[i]; if (x == N) { //nothing changes. send(K, logk); continue; } //want to remove x int w = where[x]; assert(w < K); where[C[i]] = w; cur[w] = C[i]; send(w, logk); } } } void ComputeAdvice (int *ccc, int nnn, int kkk, int mmm) { C = ccc; N = nnn; K = kkk; M = mmm; logn = 31 - __builtin_clz(N + 10); logk = 31 - __builtin_clz(K + 10); advisor_subtask3::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 int subtask; static unsigned char *A; static int N, K, R; static int logn, logk; namespace assistant_subtask3 { int where[MAXN]; int cur[MAXN]; void go() { for (int i = 0; i < K; i++) { where[i] = i; cur[i] = i; } for (int i = 0; i < N; i++) { //replace it with this int req = GetRequest(); //you replace whatever is here. int x = 0; for (int j = 0; j <= logk; j++) { int pos = (logk + 1) * i + j; x = 2 * x + A[pos]; } debug("x = %d\n", x); if (x != K) { assert(x < K); //then check what is here! //delete what is at position x, put it at debug("PutBack(%d)\n", cur[x]); PutBack(cur[x]); cur[x] = req; where[req] = x; } } } } void Assist (unsigned char *aaa, int nnn, int kkk, int rrr) { A = aaa; N = nnn; K = kkk; R = rrr; logn = 31 - __builtin_clz(N + 10); logk = 31 - __builtin_clz(K + 10); assistant_subtask3::go(); }

Compilation message (stderr)

advisor.cpp:17:2: warning: #warning static (advisor) [-Wcpp]
 #warning static (advisor)
  ^~~~~~~
advisor.cpp:19:12: warning: 'subtask' defined but not used [-Wunused-variable]
 static int subtask;
            ^~~~~~~

assistant.cpp:17:2: warning: #warning static (assistant) [-Wcpp]
 #warning static (assistant)
  ^~~~~~~
assistant.cpp:19:12: warning: 'subtask' defined but not used [-Wunused-variable]
 static int subtask;
            ^~~~~~~
#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...