oj.uz

Submission #143724

# Submission time Handle Problem Language Result Execution time Memory
143724 2019-08-15T00:54:46 Z tmwilliamlin168 Last supper (IOI12_supper) C++14
100 / 100
 234 ms 20544 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int a[2*mxN], nxt[2*mxN], d[mxN];
bool b[2*mxN];

void ComputeAdvice(int *c, int n, int k, int m) {
	iota(a, a+k, 0);
	memcpy(a+k, c, 4*n);
	map<int, int> mp;
	for(int i=0; i<n; ++i)
		mp[i]=1e9;
	for(int i=n+k-1; ~i; --i) {
		nxt[i]=mp[a[i]];
		mp[a[i]]=i;
	}
	set<array<int, 2>> s;
	for(int i=0; i<k; ++i)
		s.insert({nxt[i], i});
	for(int i=k; i<n+k; ++i) {
		if((*s.begin())[0]>i) {
			array<int, 2> c=*--s.end();
			s.erase(--s.end());
			b[c[1]]=1;
		} else
			s.erase(s.begin());
		s.insert({nxt[i], i});
	}
	memset(d, -1, 4*n);
	vector<int> v;
	for(int i=0; i<k; ++i) {
		v.push_back(i);
		d[i]=i;
	}
	for(int i=k; i<n+k; ++i) {
		if(d[a[i]]<0) {
			while(1) {
				int u=v.back();
				v.pop_back();
				if(b[d[u]]) {
					d[u]=-1;
					break;
				}
				WriteAdvice(0);
			}
			WriteAdvice(1);
		}
		d[a[i]]=i;
		v.push_back(a[i]);
	}
}
#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
bool e[mxN];

void Assist(unsigned char *a, int n, int k, int r) {
	vector<int> v;
	for(int i=0; i<k; ++i) {
		v.push_back(i);
		e[i]=1;
	}
	for(int i=0, j=0; i<n; ++i) {
		int c=GetRequest();
		if(!e[c]) {
			while(1) {
				int u=v.back();
				v.pop_back();
				if(a[j++]) {
					e[u]=0;
					PutBack(u);
					break;
				}
			}
		}
		e[c]=1;
		v.push_back(c);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 884 KB Output is correct
2 Correct 4 ms 840 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 8 ms 1264 KB Output is correct
5 Correct 10 ms 1520 KB Output is correct
6 Correct 9 ms 1520 KB Output is correct
7 Correct 10 ms 1520 KB Output is correct
8 Correct 10 ms 1520 KB Output is correct
9 Correct 10 ms 1520 KB Output is correct
10 Correct 10 ms 1776 KB Output is correct
11 Correct 11 ms 1520 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2544 KB Output is correct
2 Correct 85 ms 8952 KB Output is correct
3 Correct 206 ms 20544 KB Output is correct
4 Correct 187 ms 16632 KB Output is correct
5 Correct 172 ms 16368 KB Output is correct
6 Correct 199 ms 17232 KB Output is correct
7 Correct 195 ms 18736 KB Output is correct
8 Correct 154 ms 16984 KB Output is correct
9 Correct 155 ms 16208 KB Output is correct
10 Correct 204 ms 20080 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 15912 KB Output is correct
2 Correct 217 ms 19440 KB Output is correct
3 Correct 203 ms 19408 KB Output is correct
4 Correct 200 ms 19368 KB Output is correct
5 Correct 197 ms 18616 KB Output is correct
6 Correct 194 ms 19416 KB Output is correct
7 Correct 210 ms 19616 KB Output is correct
8 Correct 192 ms 19352 KB Output is correct
9 Correct 181 ms 19144 KB Output is correct
10 Correct 204 ms 19664 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1520 KB Output is correct
2 Correct 10 ms 1520 KB Output is correct
3 Correct 9 ms 1520 KB Output is correct
4 Correct 9 ms 1528 KB Output is correct
5 Correct 9 ms 1520 KB Output is correct
6 Correct 9 ms 1512 KB Output is correct
7 Correct 10 ms 1520 KB Output is correct
8 Correct 10 ms 1520 KB Output is correct
9 Correct 10 ms 1520 KB Output is correct
10 Correct 12 ms 2032 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 18976 KB Output is correct - 95112 bits used
2 Correct 201 ms 18952 KB Output is correct - 94230 bits used
3 Correct 206 ms 19416 KB Output is correct - 89993 bits used
4 Correct 206 ms 19168 KB Output is correct - 90338 bits used
5 Correct 204 ms 19152 KB Output is correct - 90067 bits used
6 Correct 234 ms 19312 KB Output is correct - 90108 bits used
7 Correct 199 ms 19152 KB Output is correct - 89861 bits used
8 Correct 196 ms 19416 KB Output is correct - 90427 bits used
9 Correct 198 ms 19672 KB Output is correct - 90004 bits used
10 Correct 191 ms 19496 KB Output is correct - 99665 bits used