Submission #58863

#TimeUsernameProblemLanguageResultExecution timeMemory
58863gabrielsimoesLast supper (IOI12_supper)C++17
0 / 100
2576 ms13448 KiB
#include "advisor.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 100000; typedef pair<int,int> pii; static vector<int> v[MAXN]; static bool current[MAXN]; static set<pii> nxRemove; int getNextUsage(int i) { if (v[i].empty()) return 1000000000; else { int ret = v[i].back(); return ret; } } void ComputeAdvice(int *C, int N, int K, int M) { for (int i = 0; i < N; i++) v[C[i]].push_back(i); for (int i = 0; i < N; i++) reverse(v[i].begin(), v[i].end()); for (int i = 0; i < N; i++) current[i] = false; vector<int> stk; for (int i = 0; i < K; i++) { stk.push_back(i); current[i] = true; nxRemove.insert({getNextUsage(i), i}); } for (int i = 0; i < N; i++) { // printf("i %d C[i] %d\n", i, C[i]); if (current[C[i]]) { nxRemove.erase({getNextUsage(C[i]), C[i]}); v[C[i]].pop_back(); nxRemove.insert({getNextUsage(C[i]), C[i]}); } else { auto it = prev(nxRemove.end()); int toRemove = it->second; nxRemove.erase(it); v[C[i]].pop_back(); nxRemove.insert({getNextUsage(C[i]), C[i]}); // printf("toRemove %d\n", toRemove); while (stk.back() != toRemove) { WriteAdvice(1); // printf("putBit %d\n", 1); int back = stk.back(); stk.pop_back(); stk.insert(stk.begin(), back); } WriteAdvice(0); // printf("putBit %d\n", 0); stk.pop_back(); stk.push_back(C[i]); current[C[i]] = true; current[toRemove] = false; } } }
#include "assistant.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 100000; static bool current[MAXN]; vector<int> stk; bool getBit(unsigned char *A) { static int i = 0; // printf("getBit %d\n", A[i]); return A[i++]; } void Assist(unsigned char *A, int N, int K, int R) { for (int i = 0; i < K; i++) { stk.push_back(i); current[i] = true; } for (int i = 0; i < N; i++) { int req = GetRequest(); if (current[req]) { continue; } while (getBit(A)) { int back = stk.back(); stk.pop_back(); stk.insert(stk.begin(), back); } PutBack(stk.back()); current[stk.back()] = false; stk.pop_back(); stk.push_back(req); current[req] = true; } }
#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...