oj.uz

Submission #146411

# Submission time Handle Problem Language Result Execution time Memory
146411 2019-08-23T22:25:27 Z Sorting Last supper (IOI12_supper) C++14
0 / 100
 162 ms 20184 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

const int MAXN = 1e5 + 7;

int nxt[MAXN];

struct cmp{
	bool operator()(int lvalue, int rvalue){
		return nxt[lvalue] > nxt[rvalue];
	}
};

set<int, cmp> pq;
int log_k, cnt[MAXN];
vector<int> v[MAXN];

int pos[MAXN];
vector<bool> ans;

void ComputeAdvice(int *C, int N, int K, int M) {
	for(int i = 0; i < N; ++i){
		v[C[i]].push_back(i);
	}
	for(int i = 0; i < N; ++i){
		v[i].push_back(N);
		nxt[i] = v[i][0];
		cnt[i] = 0;
	}

	for(int i = 0; i < N + K; ++i){
		ans.push_back(false);
	}

	for(int i = 0; i < K; ++i){
		pos[i] = i;
		pq.insert(i);
	}

	for(int i = 0; i < N; ++i){
		if(pq.find(C[i]) == pq.end()){
			int x = *pq.begin();
			ans[pos[x]] = false;

			pq.erase(x);
			nxt[C[i]] = v[C[i]][++cnt[C[i]]];
			pq.insert(C[i]); 

			pos[C[i]] = K + i;
		}
		else{
			ans[pos[C[i]]] = true;

			pq.erase(C[i]);
			nxt[C[i]] = v[C[i]][++cnt[C[i]]];
			pq.insert(C[i]);

			pos[C[i]] = K + i;
		}
	}

	for(bool b: ans){
		WriteAdvice(b);
	}
}

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

const int MAXN = 1e5 + 7;

vector<int> v2;
bool b[MAXN], ok[MAXN];

void Assist(unsigned char *A, int N, int K, int R) {
	for(int i = 0; i < K; ++i){
		if(!A[i]){
			ok[i] = true;
			v2.push_back(i);
		}
		b[i] = true;
	}

	for(int i = 0; i < N; ++i){
		int x = GetRequest();
		if(b[x]){
			ok[x] = !A[i + K];
			v2.push_back(x);
			continue;
		}

		while(true){
			if(b[v2.back()] && ok[v2.back()]){
				b[v2.back()] = false;
				ok[v2.back()] = false;
				PutBack(v2.back());
				ok[x] = !A[i + K];
				b[x] = true;
				v2.push_back(x);
				break;
			}
			v2.pop_back();
		}
	}
}
/*
4 2 100
2 0 3 2
*/
/*
g++ -DEVAL -Wall -static -std=c++11 -O2 -o supper grader.cpp assistant.cpp advisor.cpp
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5360 KB Output is correct
2 Incorrect 6 ms 5368 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6592 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 16880 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6072 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 18952 KB Output isn't correct - not an optimal way
2 Incorrect 139 ms 19184 KB Output isn't correct - not an optimal way
3 Incorrect 144 ms 19712 KB Output isn't correct - not an optimal way
4 Incorrect 144 ms 19480 KB Output isn't correct - not an optimal way
5 Incorrect 139 ms 19440 KB Output isn't correct - not an optimal way
6 Incorrect 162 ms 19440 KB Output isn't correct - not an optimal way
7 Incorrect 143 ms 19696 KB Output isn't correct - not an optimal way
8 Incorrect 147 ms 19624 KB Output isn't correct - not an optimal way
9 Incorrect 145 ms 19440 KB Output isn't correct - not an optimal way
10 Incorrect 143 ms 20184 KB Output isn't correct - not an optimal way