oj.uz

Submission #70726

# Submission time Handle Problem Language Result Execution time Memory
70726 2018-08-23T09:10:22 Z funcsr Last supper (IOI12_supper) C++17
100 / 100
 577 ms 177696 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, N) 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) {
    P m = P(-G[A[i]].front(), A[i]);
    assert(G[A[i]].front()==i);
    G[A[i]].pop();

    assert(colors.size()==vs.size());
    if (colors.find(A[i]) != colors.end()) {
      mark[last[A[i]]] = true;
      vs.erase(m);
      vs.insert(P(-G[A[i]].front(), A[i]));
    }
    else {
      int c = vs.begin()->_2;
      assert(colors.find(c) != colors.end());
      colors.erase(c);
      vs.erase(vs.begin());
      colors.insert(A[i]);
      vs.insert(P(-G[A[i]].front(), A[i]));
    }
    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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 135160 KB Output is correct
2 Correct 76 ms 135496 KB Output is correct
3 Correct 84 ms 135896 KB Output is correct
4 Correct 90 ms 135904 KB Output is correct
5 Correct 85 ms 136328 KB Output is correct
6 Correct 91 ms 136360 KB Output is correct
7 Correct 82 ms 136456 KB Output is correct
8 Correct 89 ms 136536 KB Output is correct
9 Correct 82 ms 136584 KB Output is correct
10 Correct 83 ms 136904 KB Output is correct
11 Correct 92 ms 136904 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 137304 KB Output is correct
2 Correct 229 ms 140008 KB Output is correct
3 Correct 558 ms 148688 KB Output is correct
4 Correct 265 ms 148688 KB Output is correct
5 Correct 273 ms 148688 KB Output is correct
6 Correct 355 ms 148688 KB Output is correct
7 Correct 393 ms 150008 KB Output is correct
8 Correct 351 ms 151200 KB Output is correct
9 Correct 238 ms 151200 KB Output is correct
10 Correct 528 ms 155576 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 155576 KB Output is correct
2 Correct 465 ms 156400 KB Output is correct
3 Correct 504 ms 157672 KB Output is correct
4 Correct 445 ms 158800 KB Output is correct
5 Correct 397 ms 159320 KB Output is correct
6 Correct 485 ms 161232 KB Output is correct
7 Correct 480 ms 162368 KB Output is correct
8 Correct 418 ms 163280 KB Output is correct
9 Correct 423 ms 164728 KB Output is correct
10 Correct 501 ms 165880 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 165880 KB Output is correct
2 Correct 77 ms 165880 KB Output is correct
3 Correct 75 ms 165880 KB Output is correct
4 Correct 98 ms 165880 KB Output is correct
5 Correct 91 ms 165880 KB Output is correct
6 Correct 75 ms 165880 KB Output is correct
7 Correct 83 ms 165880 KB Output is correct
8 Correct 88 ms 165880 KB Output is correct
9 Correct 96 ms 165880 KB Output is correct
10 Correct 83 ms 165880 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 166520 KB Output is correct - 120000 bits used
2 Correct 475 ms 168352 KB Output is correct - 122000 bits used
3 Correct 534 ms 169800 KB Output is correct - 125000 bits used
4 Correct 577 ms 170904 KB Output is correct - 125000 bits used
5 Correct 558 ms 171960 KB Output is correct - 125000 bits used
6 Correct 515 ms 173256 KB Output is correct - 125000 bits used
7 Correct 554 ms 174304 KB Output is correct - 124828 bits used
8 Correct 510 ms 175504 KB Output is correct - 124910 bits used
9 Correct 563 ms 176744 KB Output is correct - 125000 bits used
10 Correct 528 ms 177696 KB Output is correct - 125000 bits used