oj.uz

Submission #98216

# Submission time Handle Problem Language Result Execution time Memory
98216 2019-02-21T14:51:49 Z E869120 Last supper (IOI12_supper) C++14
44 / 100
 388 ms 30384 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

int post[1 << 18], I[1 << 18]; vector<int> Z[1 << 18];
bool used[1 << 18];

void ComputeAdvice(int *C, int N, int K, int M) {
	for (int i = 0; i < N; i++) Z[C[i]].push_back(i);
	for (int i = 0; i < N; i++) post[i] = (1 << 30);
	for (int i = 0; i < N; i++) {
		for (int j = (int)Z[i].size() - 2; j >= 0; j--) post[Z[i][j]] = Z[i][j + 1];
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> que;
	for (int i = 0; i < K; i++) {
		used[i] = true; I[i] = i;
		if (Z[i].size() >= 1) que.push(make_pair(Z[i][0], i));
		else que.push(make_pair((1 << 30), i));
	}
	//cout << "post = "; for (int i = 0; i < N; i++) cout << post[i] << ","; cout << endl;
	
	vector<int> L;
	for (int i = 0; i < N; i++) {
		if (used[C[i]] == false) {
			pair<int, int> G = que.top(); que.pop();
			used[G.second] = false; I[C[i]] = I[G.second]; L.push_back(I[C[i]]);
		}
		que.push(make_pair(post[i], C[i])); used[C[i]] = true;
	}
	
	long long sz = 1, size_ = 2;
	while (size_ < 1LL * K * K * K * K) { size_ *= 2; sz++; }
	
	for (int i = 0; i < L.size(); i += 4) {
		long long S1 = 0, S2 = 1;
		for (int j = 0; j < 4; j++) { if (i + j < L.size()) { S1 += 1LL * S2 * L[i + j]; S2 *= K; } }
		
		for (int j = 0; j < sz; j++) WriteAdvice((S1 / (1LL << j)) % 2);
	}
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

int LL[1 << 18], DAI[1 << 18]; bool used2[1 << 18];

void Assist(unsigned char *A, int N, int K, int R) {
	long long sz = 1, size_ = 2;
	while (size_ < 1LL * K * K * K * K) { size_ *= 2; sz++; }
	
	for (int i = 0; i < R / sz; i++) {
		long long suma = 0;
		for (int j = 0; j < sz; j++) {
			suma += A[i * sz + j] * (1LL << j);
		}
		LL[i * 4 + 0] = (suma / (1LL)) % K;
		LL[i * 4 + 1] = (suma / (1LL * K)) % K;
		LL[i * 4 + 2] = (suma / (1LL * K * K)) % K;
		LL[i * 4 + 3] = (suma / (1LL * K * K * K)) % K;
	}
	
	for (int i = 0; i < K; i++) { used2[i] = true; DAI[i] = i; }
	
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		int G = GetRequest();
		if (used2[G] == false) {
			int nex = LL[cnt]; //cout << "request = " << G << ", nex = " << nex << ", initial value = " << DAI[nex] << ", num = " << LL[cnt] << endl;
			PutBack(DAI[nex]); cnt++;
			used2[G] = true; used2[DAI[nex]] = false; DAI[nex] = G;
		}
	}
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < L.size(); i += 4) {
                  ~~^~~~~~~~~~
advisor.cpp:37:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < 4; j++) { if (i + j < L.size()) { S1 += 1LL * S2 * L[i + j]; S2 *= K; } }
                                     ~~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13056 KB Output is correct
2 Correct 9 ms 13056 KB Output is correct
3 Correct 11 ms 13056 KB Output is correct
4 Correct 13 ms 13312 KB Output is correct
5 Correct 14 ms 13568 KB Output is correct
6 Correct 21 ms 13568 KB Output is correct
7 Correct 13 ms 13568 KB Output is correct
8 Correct 26 ms 13824 KB Output is correct
9 Correct 23 ms 13568 KB Output is correct
10 Correct 19 ms 13824 KB Output is correct
11 Correct 21 ms 13752 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 14336 KB Output is correct
2 Correct 102 ms 17664 KB Output is correct
3 Correct 283 ms 28216 KB Output is correct
4 Correct 217 ms 24296 KB Output is correct
5 Correct 278 ms 25880 KB Output is correct
6 Correct 300 ms 26376 KB Output is correct
7 Correct 258 ms 26040 KB Output is correct
8 Correct 261 ms 26880 KB Output is correct
9 Correct 162 ms 20536 KB Output is correct
10 Correct 237 ms 25496 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 22712 KB Output is correct
2 Correct 278 ms 25648 KB Output is correct
3 Correct 289 ms 25872 KB Output is correct
4 Correct 325 ms 24928 KB Output is correct
5 Correct 212 ms 22392 KB Output is correct
6 Correct 230 ms 25680 KB Output is correct
7 Correct 275 ms 25328 KB Output is correct
8 Correct 378 ms 30384 KB Output is correct
9 Correct 162 ms 20984 KB Output is correct
10 Correct 255 ms 25824 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 13312 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 39.0

# Verdict Execution time Memory Grader output
1 Partially correct 270 ms 26320 KB Output is partially correct - 746634 bits used
2 Partially correct 277 ms 25952 KB Output is partially correct - 717402 bits used
3 Partially correct 260 ms 25672 KB Output is partially correct - 700625 bits used
4 Partially correct 301 ms 25616 KB Output is partially correct - 700153 bits used
5 Partially correct 331 ms 25656 KB Output is partially correct - 698796 bits used
6 Partially correct 232 ms 25616 KB Output is partially correct - 700330 bits used
7 Partially correct 271 ms 26128 KB Output is partially correct - 699268 bits used
8 Partially correct 227 ms 25872 KB Output is partially correct - 701451 bits used
9 Partially correct 262 ms 25616 KB Output is partially correct - 700979 bits used
10 Partially correct 388 ms 29568 KB Output is partially correct - 1098993 bits used