Submission #58456

#TimeUsernameProblemLanguageResultExecution timeMemory
58456kingpig9Last supper (IOI12_supper)C++11
0 / 100
236 ms27736 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() { vector<int> ans = getans(); vector<vector<int>> rpos(N + 1, vector<int> ()); for (int i = 0; i < ans.size(); i++) { rpos[ans[i]].push_back(i); } //will it be removed before it's used? vector<int> firstrem(N + 1, N); vector<int> lastuse(N + 1, N); for (int i = 0; i < N; i++) { if (ans[i] != N) { firstrem[ans[i]] = i; } lastuse[C[i]] = i; } for (int i = 0; i < K; i++) { WriteAdvice(lastuse[i] == N || firstrem[i] > lastuse[i]); } for (int i = 0; i < N; i++) { //what do you remove? ans[i]. //what do you replace it with? C[i]. //is it going to be removed before it's used again? if (ans[i] == N) { WriteAdvice(1); //good } else { if (i != lastuse[C[i]]) { auto it = upper_bound(all(rpos[C[i]]), i); if (it != rpos[C[i]].end() && *it < lastuse[C[i]]) { //yes it will be removed WriteAdvice(0); } else { WriteAdvice(1); } } else { WriteAdvice(1); } } } } 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)
  ^~~~~~~
advisor.cpp: In function 'void go()':
advisor.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~

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...