oj.uz

Submission #365387

# Submission time Handle Problem Language Result Execution time Memory
365387 2021-02-11T14:43:26 Z Seanliu Last supper (IOI12_supper) C++14
100 / 100
 212 ms 74508 KB 
#include "advisor.h"
#include <iostream>
#include <utility>
#include <cassert>
#include <set>
#include <deque>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;

struct Obj{
	int time, col;
	Obj(int time = 0, int col = 0): time(time), col(col){}
	const bool operator<(const Obj &o) const {
		return col == o.col ? time < o.time : col < o.col;
	}
};

const int maxN = 1e5 + 326;
bool has[maxN], advice[maxN << 1];
set <pair<int, Obj>> st;
deque<int> dq[maxN];


void ComputeAdvice(int *C, int N, int K, int M) {
	fill(has, has + K, 1);
	for(int i = 0; i < N; i++){
		dq[C[i]].push_back(i);
	}
	for(int i = 0; i < K; i++){
		int furt = dq[i].size() ? dq[i].front() : maxN;
		st.insert({furt, Obj(i - K, i)});
	}
	//int bc = 0, key;
	//while((1 << bc) < N + 1) bc++;
	for(int i = 0; i < N; i++){ //thirteen bits lol
		//key = -1;
		if(has[C[i]]){
			int furt = dq[C[i]].size() ? dq[C[i]].front() : maxN;
			st.erase(st.lower_bound({furt, Obj(-maxN, C[i])}));
		} else {
			auto it = --st.end();
			advice[it->S.time + K] = 1;
			st.erase(st.find({it->F, it->S}));
			has[it->S.col] = false;
			//key = it->S.col;
		}
		//if(key == -1) key = (1 << bc) - 1;
		while(dq[C[i]].size() && dq[C[i]].front() <= i) dq[C[i]].pop_front();
		int furt = dq[C[i]].size() ? dq[C[i]].front() : maxN;
		st.insert({furt, Obj(i, C[i])});
		has[C[i]] = true;
		//for(int j = 0; j < bc; j++) WriteAdvice((key >> j) & 1);
	}
	for(int i = 0; i < N + K; i++) WriteAdvice(advice[i]);
}


#include <iostream>
#include <set>
#include <utility>
#include <queue>
#include <cassert>
#define pii pair<int,int>
#define F first
#define S second
#include "assistant.h"
using namespace std;


bool cur[101010], inq[101010];
queue<int> que;

void Assist(unsigned char *A, int N, int K, int R) {
	//assert(R == N + K);	
	for(int i = 0; i < K; i++){
		cur[i] = true;
		if(A[i]) que.push(i);
	}
	//int bc = 0, key;
	//while((1 << bc) < N + 1) bc++;
	for(int i = 0; i < N; i++){
		int r = GetRequest();	
		if(!cur[r]){
			int c = que.front(); que.pop();
			cur[c] = false;
			PutBack(c);
		} 
		cur[r] = true;
		if(A[i + K]) que.push(r);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 68324 KB Output is correct
2 Correct 60 ms 68196 KB Output is correct
3 Correct 55 ms 68588 KB Output is correct
4 Correct 55 ms 68920 KB Output is correct
5 Correct 54 ms 68360 KB Output is correct
6 Correct 57 ms 68508 KB Output is correct
7 Correct 56 ms 69084 KB Output is correct
8 Correct 59 ms 68500 KB Output is correct
9 Correct 57 ms 68488 KB Output is correct
10 Correct 58 ms 68508 KB Output is correct
11 Correct 57 ms 68616 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 68780 KB Output is correct
2 Correct 123 ms 70512 KB Output is correct
3 Correct 201 ms 73736 KB Output is correct
4 Correct 146 ms 71304 KB Output is correct
5 Correct 151 ms 71336 KB Output is correct
6 Correct 180 ms 71848 KB Output is correct
7 Correct 189 ms 72628 KB Output is correct
8 Correct 164 ms 72996 KB Output is correct
9 Correct 133 ms 71256 KB Output is correct
10 Correct 196 ms 73424 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 72216 KB Output is correct
2 Correct 195 ms 73032 KB Output is correct
3 Correct 196 ms 73216 KB Output is correct
4 Correct 198 ms 73236 KB Output is correct
5 Correct 196 ms 72620 KB Output is correct
6 Correct 189 ms 74308 KB Output is correct
7 Correct 195 ms 74236 KB Output is correct
8 Correct 178 ms 74128 KB Output is correct
9 Correct 182 ms 74252 KB Output is correct
10 Correct 212 ms 74508 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 68612 KB Output is correct
2 Correct 57 ms 68740 KB Output is correct
3 Correct 56 ms 68360 KB Output is correct
4 Correct 57 ms 68488 KB Output is correct
5 Correct 57 ms 68516 KB Output is correct
6 Correct 56 ms 68360 KB Output is correct
7 Correct 57 ms 68488 KB Output is correct
8 Correct 56 ms 68504 KB Output is correct
9 Correct 58 ms 68488 KB Output is correct
10 Correct 60 ms 68752 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 72772 KB Output is correct - 120000 bits used
2 Correct 195 ms 72724 KB Output is correct - 122000 bits used
3 Correct 205 ms 73148 KB Output is correct - 125000 bits used
4 Correct 197 ms 73148 KB Output is correct - 125000 bits used
5 Correct 187 ms 73224 KB Output is correct - 125000 bits used
6 Correct 198 ms 73148 KB Output is correct - 125000 bits used
7 Correct 195 ms 73352 KB Output is correct - 124828 bits used
8 Correct 187 ms 73148 KB Output is correct - 124910 bits used
9 Correct 205 ms 73332 KB Output is correct - 125000 bits used
10 Correct 180 ms 73084 KB Output is correct - 125000 bits used