oj.uz

Submission #309191

# Submission time Handle Problem Language Result Execution time Memory
309191 2020-10-02T21:24:45 Z Namnamseo Last supper (IOI12_supper) C++17
100 / 100
 109 ms 10224 KB 
#include <set>
#include <algorithm>
#include "advisor.h"
using namespace std;
using pp=pair<int, int>;

#define rep(i, N) for(int i=0; i<(N); ++i)

static int nut[100010];
static int lp[100010];
static int first[100010];
static bool isin[100010];

static bool weak[100010];
static bool weak0[100010];

#include <cstdio>

void ComputeAdvice(int *C, int N, int K, int M) {
	set<pp> s;

	rep(i, N) lp[i] = -1, isin[i] = false;
	rep(i, K) first[i] = N;
	rep(i, N) {
		int c = C[i];
		if (lp[c] != -1) {
			nut[lp[c]] = i;
		}
		if (c < K && first[c] == N) first[c] = i;
		lp[c] = i;
		nut[i] = N;
		weak[i] = false;
	}

	rep(i, K) {
		s.emplace(first[i], -1-i);
		isin[i] = true;
	}

	rep(i, N) {
		int c = C[i];
		if (isin[c]) {
			s.erase(s.lower_bound(pp(i, -1)));
		} else {
			set<pp>::iterator it = --s.end();
			if (it->second < 0) {
				int t = (-(it->second)) - 1;
				isin[t] = false;
				weak0[t] = true;
			} else {
				isin[C[it->second]] = false;
				weak[it->second] = true;
			}
			s.erase(it);
		}
		s.emplace(nut[i], i);
		isin[c] = true;
	}

	rep(i, K) WriteAdvice(weak0[i]);
	rep(i, N) WriteAdvice(weak[i]);
}

#include "assistant.h"
#define rep(i, N) for(int i=0; i<(N); ++i)

static bool isin[100010];
static int q[100010];

#include <cstdio>

void Assist(unsigned char *A, int N, int K, int R) {
	int hd = 0, tl = 0;

	rep(i, K) {
		isin[i] = true;
		if (A[i] == 1) {
			q[hd++] = i;
		}
	}

	rep(i, N) {
		int req = GetRequest();
		if (!isin[req]) {
			isin[q[tl]] = false;
			PutBack(q[tl]);
			++tl;
		}

		if (A[K+i] == 1) {
			q[hd++] = req;
		}

		isin[req] = true;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 904 KB Output is correct
2 Correct 1 ms 888 KB Output is correct
3 Correct 2 ms 968 KB Output is correct
4 Correct 3 ms 1232 KB Output is correct
5 Correct 5 ms 1136 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 1204 KB Output is correct
8 Correct 5 ms 1168 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 6 ms 1024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 47 ms 3944 KB Output is correct
3 Correct 102 ms 10224 KB Output is correct
4 Correct 74 ms 6384 KB Output is correct
5 Correct 77 ms 6384 KB Output is correct
6 Correct 88 ms 7152 KB Output is correct
7 Correct 104 ms 8688 KB Output is correct
8 Correct 81 ms 7928 KB Output is correct
9 Correct 74 ms 6128 KB Output is correct
10 Correct 107 ms 9712 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7408 KB Output is correct
2 Correct 104 ms 8944 KB Output is correct
3 Correct 109 ms 9200 KB Output is correct
4 Correct 106 ms 8944 KB Output is correct
5 Correct 104 ms 8688 KB Output is correct
6 Correct 105 ms 9096 KB Output is correct
7 Correct 105 ms 8944 KB Output is correct
8 Correct 93 ms 9200 KB Output is correct
9 Correct 97 ms 8944 KB Output is correct
10 Correct 105 ms 8944 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1160 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 5 ms 1216 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1212 KB Output is correct
6 Correct 5 ms 1072 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 5 ms 1104 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 7 ms 1280 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 8432 KB Output is correct - 120000 bits used
2 Correct 104 ms 9128 KB Output is correct - 122000 bits used
3 Correct 103 ms 9200 KB Output is correct - 125000 bits used
4 Correct 104 ms 9200 KB Output is correct - 125000 bits used
5 Correct 104 ms 8944 KB Output is correct - 125000 bits used
6 Correct 107 ms 9200 KB Output is correct - 125000 bits used
7 Correct 105 ms 8944 KB Output is correct - 124828 bits used
8 Correct 107 ms 8944 KB Output is correct - 124910 bits used
9 Correct 107 ms 9144 KB Output is correct - 125000 bits used
10 Correct 96 ms 8944 KB Output is correct - 125000 bits used