Submission #1016977

#TimeUsernameProblemLanguageResultExecution timeMemory
1016977lovrotLast supper (IOI12_supper)C++17
0 / 100
158 ms143020 KiB
#include <cstdio> #include <vector> #include <set> #include <stack> #include <algorithm> #include "advisor.h" #include <cstring> #include <cassert> #define X first #define Y second #define PB push_back using namespace std; typedef pair<int, int> pii; const int N = 1e5 + 10; int out[N], lst[N], dea[N]; stack<int> nxt[N]; set<pii> s; void ComputeAdvice(int *c, int n, int k, int m) { memset(lst, -1, sizeof(lst)); for(int i = 0; i < n; ++i) { nxt[i].push(N); } for(int i = n - 1; i >= 0; --i) { nxt[c[i]].push(i); } for(int i = 0; i < k; ++i) { s.insert({nxt[i].top(), i}); } for(int i = 0; i < n; ++i) { auto it = s.lower_bound({nxt[c[i]].top(), c[i]}); nxt[c[i]].pop(); if(it != s.end() && it->Y == c[i]) { out[i] = -1; s.erase(it); } else { int obr = prev(s.end())->Y; out[i] = obr; dea[lst[obr]] = 1; s.erase({nxt[obr].top(), obr}); } s.insert({nxt[c[i]].top(), c[i]}); lst[c[i]] = i + k; } for(auto i : s) { dea[lst[i.Y]] = 1; } for(int i = 0; i < k + n; ++i) { WriteAdvice(dea[i]); } }
#include <cstdio> #include <set> #include "assistant.h" #include <algorithm> #include <cassert> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 1e5 + 10; // GetRequest() // PutBack(int x) set<int> act[2]; void Assist(unsigned char *a, int n, int k, int r) { for(int i = 0; i < k; ++i) { act[a[i]].insert(i); } for(int i = 0; i < n; ++i) { int x = GetRequest(); bool d = a[i + k]; auto it = act[0].lower_bound(x); if(it != act[0].end() && *it == x) { act[0].erase(it); } else { int out = *act[1].begin(); act[1].erase(act[1].begin()); PutBack(out); } act[d].insert(x); } }
#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...