oj.uz

Submission #623178

# Submission time Handle Problem Language Result Execution time Memory
623178 2022-08-05T09:37:24 Z ollel Last supper (IOI12_supper) C++14
100 / 100
 286 ms 11156 KB 
using namespace std;
#include <bits/stdc++.h>
#include "advisor.h"


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<bool> vb;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
//
// void WriteAdvice(int x) {
//   cout << x << " ";
// }

void ComputeAdvice(int *c, int n, int k, int m) {
  bool debug = false;
  int ans = 0;
  set<int> scaffold;
  rep(i,0,k) scaffold.insert(i);


  vi advice(2*n, 0);
  vi added(n, 0);
  rep(i,0,k) added[i] = i;

  vi nextOccurenceOfColor(n,1e9);
  vi sweep(n,1e9);
  for (int i = n - 1; i >= 0; i--) {
    nextOccurenceOfColor[i] = sweep[c[i]];
    sweep[c[i]] = i;
  }

  priority_queue<pair<int,int>> pq;
  rep(i,0,k) pq.push({sweep[i], i});

  if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
  rep(i,0,n) {
    int color = c[i];
    added[color] = n+i;


    if (scaffold.find(color) != scaffold.end()) {
      if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
      pq.push({nextOccurenceOfColor[i], c[i]});
      continue;
    }


    int toRemove = -1;
    while (scaffold.find(toRemove) == scaffold.end()) {
      assert(pq.size() != 0);
      pair<int,int> res = pq.top(); pq.pop();
      if (debug) cout << "popped " << res.first << ", "<< res.second << endl;
      toRemove = res.second;
    }

    pq.push({nextOccurenceOfColor[i], c[i]});

    advice[added[toRemove]] = 1;
    if (debug) cout << "advice at " << added[toRemove] << endl;
    scaffold.erase(toRemove);
    ans++;

    scaffold.insert(c[i]);
    if (debug) cout << "pushing " << c[i] << " with next occ " << nextOccurenceOfColor[i] << endl;
    if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;

  }
  rep(i,0,2*n) WriteAdvice(advice[i]);
  if (debug) cout << "\nanswer: " << ans << endl;
}

// int main() {
//   int c[] ={4, 1, 2, 1, 2, 1, 4, 2};
//   ComputeAdvice(c, 8, 2, -1);
// }

using namespace std;
#include <bits/stdc++.h>
#include "assistant.h"


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<bool> vb;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back



void Assist(unsigned char *a, int n, int k, int r) {
  set<int> scaffold;
  rep(i,0,k) scaffold.insert(i);

  vector<int> advice(2*n);
  rep(i,0,2*n) advice[i] = a[i];
  queue<int> q;
  rep(i,0,k) if (advice[i] == 1) q.push(i);

  rep(i,0,n) {
    int nextColor = GetRequest();
    if (scaffold.find(nextColor) == scaffold.end()) {
      int rem = q.front(); q.pop();
      PutBack(rem);
      scaffold.erase(rem);
      scaffold.insert(nextColor);
    }
    if (advice[n + i] == 1) {
      q.push(nextColor);
    }
  }
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:40:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   40 |   if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
      |   ^~
advisor.cpp:40:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   40 |   if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
      |                                                        ^~~~
advisor.cpp:47:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   47 |       if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
      |       ^~
advisor.cpp:47:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   47 |       if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
      |                                                            ^~~~
advisor.cpp:70:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   70 |     if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
      |     ^~
advisor.cpp:70:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   70 |     if (debug) for (auto k : scaffold) cout << k << " "; cout << endl;
      |                                                          ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 516 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 3 ms 780 KB Output is correct
4 Correct 6 ms 672 KB Output is correct
5 Correct 10 ms 924 KB Output is correct
6 Correct 11 ms 944 KB Output is correct
7 Correct 10 ms 1044 KB Output is correct
8 Correct 11 ms 944 KB Output is correct
9 Correct 12 ms 940 KB Output is correct
10 Correct 12 ms 1024 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1404 KB Output is correct
2 Correct 112 ms 4552 KB Output is correct
3 Correct 274 ms 11156 KB Output is correct
4 Correct 235 ms 6944 KB Output is correct
5 Correct 229 ms 7108 KB Output is correct
6 Correct 259 ms 7916 KB Output is correct
7 Correct 278 ms 9736 KB Output is correct
8 Correct 216 ms 8672 KB Output is correct
9 Correct 202 ms 6836 KB Output is correct
10 Correct 259 ms 10696 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 7152 KB Output is correct
2 Correct 285 ms 10144 KB Output is correct
3 Correct 263 ms 10152 KB Output is correct
4 Correct 261 ms 10212 KB Output is correct
5 Correct 242 ms 9764 KB Output is correct
6 Correct 261 ms 10232 KB Output is correct
7 Correct 274 ms 10320 KB Output is correct
8 Correct 284 ms 9764 KB Output is correct
9 Correct 232 ms 10276 KB Output is correct
10 Correct 286 ms 10160 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1020 KB Output is correct
2 Correct 13 ms 920 KB Output is correct
3 Correct 11 ms 936 KB Output is correct
4 Correct 12 ms 900 KB Output is correct
5 Correct 15 ms 828 KB Output is correct
6 Correct 14 ms 940 KB Output is correct
7 Correct 12 ms 980 KB Output is correct
8 Correct 13 ms 916 KB Output is correct
9 Correct 11 ms 948 KB Output is correct
10 Correct 12 ms 1324 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 8644 KB Output is correct - 200000 bits used
2 Correct 254 ms 8772 KB Output is correct - 200000 bits used
3 Correct 257 ms 9184 KB Output is correct - 200000 bits used
4 Correct 254 ms 9084 KB Output is correct - 200000 bits used
5 Correct 254 ms 9076 KB Output is correct - 200000 bits used
6 Correct 257 ms 9192 KB Output is correct - 200000 bits used
7 Correct 260 ms 9300 KB Output is correct - 199678 bits used
8 Correct 264 ms 9056 KB Output is correct - 200000 bits used
9 Correct 255 ms 9016 KB Output is correct - 200000 bits used
10 Correct 252 ms 8540 KB Output is correct - 200000 bits used