oj.uz

Submission #1017398

# Submission time Handle Problem Language Result Execution time Memory
1017398 2024-07-09T07:45:22 Z lovrot Last supper (IOI12_supper) C++17
100 / 100
 179 ms 143952 KB 
#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]);
	}
}

#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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