답안 #1017398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017398	2024-07-09T07:45:22 Z	lovrot	최후의 만찬 (IOI12_supper)	C++17	100 / 100	179 ms	143952 KB

advisor

#include <cstdio>
#include <vector> 
#include <set>
#include <stack>
#include <algorithm>
#include "advisor.h"
#include <cstring> 
#include <cassert>

#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef pair<int, int> pii;

const int N = 2e5 + 10;

int lst[N], dea[N];

stack<int> nxt[N];
set<pii> s;

void ComputeAdvice(int *c, int n, int k, int m) {
	memset(lst, -1, sizeof(lst));

	for(int i = 0; i < n; ++i) { 
		nxt[i].push(N);
	}

	for(int i = n - 1; i >= 0; --i) { 
		nxt[c[i]].push(i);
	}

	for(int i = 0; i < k; ++i) {
		lst[i] = i;
		s.insert({nxt[i].top(), i});
	}

	for(int i = 0; i < n; ++i) {
		auto it = s.find({nxt[c[i]].top(), c[i]}); 
		nxt[c[i]].pop();
		if(it != s.end()) { 
			s.erase(it);
		} else {
			int obr = prev(s.end())->Y;
			dea[lst[obr]] = 1;
			s.erase(prev(s.end()));
		}	
		s.insert({nxt[c[i]].top(), c[i]});
		lst[c[i]] = i + k;
	}

	for(auto i : s) { 
		dea[lst[i.Y]] = 1;
	}

	for(int i = 0; i < k + n; ++i) {
		WriteAdvice(dea[i]);
	}
}

assistant

#include <cstdio>
#include <set>
#include "assistant.h"
#include <algorithm>
#include <cassert>

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;

set<int> act[2];

void Assist(unsigned char *a, int n, int k, int r) {
	for(int i = 0; i < k; ++i) { 
		act[a[i]].insert(i);
	}

	for(int i = 0; i < n; ++i) { 
		int x = GetRequest();
		bool d = a[i + k];

		auto it = act[0].find(x);
		if(it != act[0].end()) { 
			act[0].erase(it);
		} else {
			int out = *act[1].begin();
			act[1].erase(act[1].begin());
			PutBack(out);
		}
		act[d].insert(x);
	}
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	136120 KB	Output is correct
2	Correct	55 ms	136120 KB	Output is correct
3	Correct	61 ms	136208 KB	Output is correct
4	Correct	59 ms	136160 KB	Output is correct
5	Correct	59 ms	136172 KB	Output is correct
6	Correct	61 ms	136344 KB	Output is correct
7	Correct	54 ms	136288 KB	Output is correct
8	Correct	61 ms	136184 KB	Output is correct
9	Correct	64 ms	136180 KB	Output is correct
10	Correct	55 ms	136436 KB	Output is correct
11	Correct	60 ms	136172 KB	Output is correct

Subtask #2

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	136444 KB	Output is correct
2	Correct	105 ms	138512 KB	Output is correct
3	Correct	145 ms	143952 KB	Output is correct
4	Correct	101 ms	140488 KB	Output is correct
5	Correct	107 ms	140304 KB	Output is correct
6	Correct	119 ms	140820 KB	Output is correct
7	Correct	141 ms	142368 KB	Output is correct
8	Correct	126 ms	141932 KB	Output is correct
9	Correct	100 ms	140228 KB	Output is correct
10	Correct	156 ms	143468 KB	Output is correct

Subtask #3

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	125 ms	141328 KB	Output is correct
2	Correct	144 ms	142932 KB	Output is correct
3	Correct	143 ms	142900 KB	Output is correct
4	Correct	169 ms	142908 KB	Output is correct
5	Correct	154 ms	142268 KB	Output is correct
6	Correct	144 ms	142764 KB	Output is correct
7	Correct	147 ms	142840 KB	Output is correct
8	Correct	122 ms	142872 KB	Output is correct
9	Correct	135 ms	142652 KB	Output is correct
10	Correct	151 ms	142932 KB	Output is correct

Subtask #4

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	136168 KB	Output is correct
2	Correct	58 ms	136176 KB	Output is correct
3	Correct	60 ms	136268 KB	Output is correct
4	Correct	58 ms	136336 KB	Output is correct
5	Correct	65 ms	136428 KB	Output is correct
6	Correct	58 ms	136168 KB	Output is correct
7	Correct	58 ms	136484 KB	Output is correct
8	Correct	57 ms	136324 KB	Output is correct
9	Correct	62 ms	136356 KB	Output is correct
10	Correct	55 ms	136700 KB	Output is correct

Subtask #5

39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	139 ms	142388 KB	Output is correct - 120000 bits used
2	Correct	144 ms	142744 KB	Output is correct - 122000 bits used
3	Correct	146 ms	142856 KB	Output is correct - 125000 bits used
4	Correct	138 ms	143016 KB	Output is correct - 125000 bits used
5	Correct	149 ms	142904 KB	Output is correct - 125000 bits used
6	Correct	166 ms	142844 KB	Output is correct - 125000 bits used
7	Correct	171 ms	142964 KB	Output is correct - 124828 bits used
8	Correct	170 ms	142912 KB	Output is correct - 124910 bits used
9	Correct	154 ms	142912 KB	Output is correct - 125000 bits used
10	Correct	179 ms	142780 KB	Output is correct - 125000 bits used