oj.uz

Submission #146471

# Submission time Handle Problem Language Result Execution time Memory
146471 2019-08-24T08:39:28 Z Sorting Last supper (IOI12_supper) C++14
100 / 100
 187 ms 21232 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

const int MAXN = 1e5 + 7;

int nxt[MAXN];

struct cmp{
	bool operator()(pair<int, int> lvalue, pair<int, int> rvalue){
		if(lvalue.second != rvalue.second){
			return lvalue.second > rvalue.second;
		}

		return lvalue.first > rvalue.first;
	}
};

set<pair<int, int>, cmp> pq;
int 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, nxt[i]});
	}

	for(int i = 0; i < N; ++i){
		if(pq.find({C[i], nxt[C[i]]}) == pq.end()){
			pair<int, int> p = *pq.begin();
			int x = p.first;

			ans[pos[x]] = false;

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

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

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

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

	while(!pq.empty()){
		pair<int, int> p = *pq.begin();
		int x = p.first;

		ans[pos[x]] = true;

		pq.erase(p);
	}

	for(bool b: ans){
		WriteAdvice(b);
		//cout << b << " ";
	}
	//cout << endl;
}

#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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5360 KB Output is correct
2 Correct 7 ms 5360 KB Output is correct
3 Correct 7 ms 5616 KB Output is correct
4 Correct 9 ms 5872 KB Output is correct
5 Correct 10 ms 5976 KB Output is correct
6 Correct 11 ms 6136 KB Output is correct
7 Correct 11 ms 6128 KB Output is correct
8 Correct 11 ms 6128 KB Output is correct
9 Correct 11 ms 5872 KB Output is correct
10 Correct 12 ms 6128 KB Output is correct
11 Correct 11 ms 6128 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6896 KB Output is correct
2 Correct 69 ms 12480 KB Output is correct
3 Correct 166 ms 21232 KB Output is correct
4 Correct 108 ms 17904 KB Output is correct
5 Correct 119 ms 17744 KB Output is correct
6 Correct 141 ms 18424 KB Output is correct
7 Correct 187 ms 19696 KB Output is correct
8 Correct 142 ms 18440 KB Output is correct
9 Correct 92 ms 18672 KB Output is correct
10 Correct 175 ms 20824 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17088 KB Output is correct
2 Correct 164 ms 20208 KB Output is correct
3 Correct 166 ms 20464 KB Output is correct
4 Correct 165 ms 20208 KB Output is correct
5 Correct 160 ms 20024 KB Output is correct
6 Correct 172 ms 20208 KB Output is correct
7 Correct 169 ms 20208 KB Output is correct
8 Correct 152 ms 20208 KB Output is correct
9 Correct 150 ms 20720 KB Output is correct
10 Correct 166 ms 20408 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6128 KB Output is correct
2 Correct 11 ms 6384 KB Output is correct
3 Correct 10 ms 5872 KB Output is correct
4 Correct 11 ms 5872 KB Output is correct
5 Correct 12 ms 5872 KB Output is correct
6 Correct 10 ms 6128 KB Output is correct
7 Correct 11 ms 5872 KB Output is correct
8 Correct 11 ms 6128 KB Output is correct
9 Correct 12 ms 6128 KB Output is correct
10 Correct 13 ms 6640 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 19752 KB Output is correct - 120000 bits used
2 Correct 165 ms 19896 KB Output is correct - 122000 bits used
3 Correct 167 ms 20208 KB Output is correct - 125000 bits used
4 Correct 167 ms 20464 KB Output is correct - 125000 bits used
5 Correct 174 ms 20208 KB Output is correct - 125000 bits used
6 Correct 167 ms 20208 KB Output is correct - 125000 bits used
7 Correct 164 ms 20464 KB Output is correct - 124828 bits used
8 Correct 165 ms 20208 KB Output is correct - 124910 bits used
9 Correct 177 ms 20304 KB Output is correct - 125000 bits used
10 Correct 152 ms 20208 KB Output is correct - 125000 bits used