답안 #309191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309191	2020-10-02T21:24:45 Z	Namnamseo	최후의 만찬 (IOI12_supper)	C++17	100 / 100	109 ms	10224 KB

advisor

#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]);
}

assistant

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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