oj.uz

Submission #70696

# Submission time Handle Problem Language Result Execution time Memory
70696 2018-08-23T08:53:40 Z funcsr Last supper (IOI12_supper) C++17
0 / 100
 496 ms 174112 KB 
#include "advisor.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int last[100000];
queue<int> G[100000];
bool mark[200000];

void ComputeAdvice(int *A, int N, int K, int M) {
  rep(i, N) G[A[i]].push(i);
  rep(i, K) G[i].push(INF);
  set<int> colors;
  set<P> vs;
  rep(i, K) vs.insert(P(-G[i].front(), i)), last[i] = i, colors.insert(i);
  rep(i, N) {
    G[A[i]].pop();
    if (colors.find(A[i]) != colors.end()) {
      mark[last[A[i]]] = true;
    }
    else {
      int c = vs.begin()->_2;
      colors.erase(c);
      vs.erase(vs.begin());
      colors.insert(A[i]);
      vs.insert(P(-G[c].front(), c));
    }
    last[A[i]] = i+K;
  }
  //rep(i, N+K) cout<<mark[i];cout<<"\n";
  rep(i, N+K) WriteAdvice(mark[i]);
}

#include "assistant.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

void Assist(unsigned char *A, int N, int K, int R) {
  assert(R==N+K);
  set<int> colors;
  queue<int> free;
  set<int> keep;
  rep(i, K) {
    colors.insert(i);
    if (A[i]) keep.insert(i);
    else free.push(i);
  }
  rep(i, N) {
    int req = GetRequest();
    if (colors.find(req) != colors.end()) {
      assert(keep.find(req) != keep.end());
      keep.erase(req);
      if (A[i+K]) keep.insert(req);
      else free.push(req);
    }
    else {
      assert(!free.empty());
      PutBack(free.front());
      colors.erase(free.front());
      free.pop();
      if (A[i+K]) keep.insert(req);
      else free.push(req);
      colors.insert(req);
    }
  }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 135416 KB Output is correct
2 Correct 83 ms 135632 KB Output is correct
3 Correct 75 ms 136080 KB Output is correct
4 Runtime error 79 ms 136144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 98 ms 137528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 148312 KB Output is correct
2 Correct 424 ms 151872 KB Output is correct
3 Correct 429 ms 153472 KB Output is correct
4 Correct 471 ms 153600 KB Output is correct
5 Runtime error 379 ms 153600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 153600 KB Output is correct
2 Correct 93 ms 153600 KB Output is correct
3 Runtime error 100 ms 153600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 369 ms 155984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 496 ms 162048 KB Output is correct - 122000 bits used
3 Correct 445 ms 163704 KB Output is correct - 125000 bits used
4 Correct 451 ms 164856 KB Output is correct - 125000 bits used
5 Correct 395 ms 165752 KB Output is correct - 125000 bits used
6 Correct 425 ms 167400 KB Output is correct - 125000 bits used
7 Correct 391 ms 168568 KB Output is correct - 124828 bits used
8 Correct 465 ms 169296 KB Output is correct - 124910 bits used
9 Correct 486 ms 170312 KB Output is correct - 125000 bits used
10 Runtime error 377 ms 174112 KB Execution killed with signal 11 (could be triggered by violating memory limits)