oj.uz

Submission #73867

# Submission time Handle Problem Language Result Execution time Memory
73867 2018-08-29T07:38:41 Z FLDutchman Last supper (IOI12_supper) C++14
34 / 100
 507 ms 33992 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define pb push_back
#define fst first
#define snd second
#define FOR(i,l,r) for(int i = (l); i < (r); i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int NUM_BITS;

set<int> q;
vi C;
void ComputeAdvice(int *c, int N, int K, int M) {
	FOR(i,0,N) C.pb(c[i]);
	FOR(i,0,N) C.pb(i);
	NUM_BITS = K <= 5000 ? 13 : 15;
	vi ne(N, -1), last(N,-1);
	FOR(i,0,C.size()){
		if(last[C[i]] != -1) ne[last[C[i]]] = i;
		last[C[i]] = i;
	}
	//for(int k : ne) cout << k << endl;
	vi idx(N, -1);
	for(int i = 0; i < C.size(); i++) {
		if(C[i] < K and idx[C[i]] == -1) {
			q.insert(i);
			idx[C[i]] = C[i];
		}
	}
	//FOR(i,0,K) cout << idx[i] << endl;
	FOR(i, 0, N) {
		if(idx[C[i]] == -1){
			int t = *prev(q.end());
			q.erase(t);
			q.insert(ne[i]);
			idx[C[i]] = idx[C[t]];
			idx[C[t]] = -1;
			int n = idx[C[i]];
			//cout << n << endl;
			//cout << C[t] << endl;
			FOR(i, 0, NUM_BITS) {
				WriteAdvice((n>>i)&1);
			}
		} else {
			assert(*q.begin() == i);
			q.erase(i);
			q.insert(ne[i]);
		}
	}
}

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

typedef int INT;

#define pb push_back
#define fst first
#define snd second
#define FOR(i,l,r) for(int i = (l); i < (r); i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int nb;

void Assist(unsigned char *A, int N, int K, int R) {
	int k = 0;
	nb = K <= 5000 ? 13 : 15;
 	vi idx(N, -1);
 	vi arr(K, 0);
 	FOR(i, 0, K) idx[i] = arr[i] = i;
 	FOR(i, 0, N){
 		int t = GetRequest();
 		if(idx[t] == -1) {
 			int n = 0;
 			FOR(i, 0, nb) n += A[k++] << i;
 			//cout << n << endl;
 			//cout << arr[n] << endl;
 			//cout << arr[n] << endl;
 			PutBack(arr[n]);
 			int an = arr[n];
 			arr[n] = t;
 			idx[an] = -1;
 			idx[t] = n;
 		}
 	}
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                                       ^
advisor.cpp:26:2: note: in expansion of macro 'FOR'
  FOR(i,0,C.size()){
  ^~~
advisor.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < C.size(); i++) {
                 ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 752 KB Output is correct
2 Correct 7 ms 1124 KB Output is correct
3 Correct 7 ms 1384 KB Output is correct
4 Correct 13 ms 1560 KB Output is correct
5 Correct 19 ms 2088 KB Output is correct
6 Correct 26 ms 2088 KB Output is correct
7 Correct 11 ms 2088 KB Output is correct
8 Correct 24 ms 2280 KB Output is correct
9 Correct 20 ms 2320 KB Output is correct
10 Correct 20 ms 2504 KB Output is correct
11 Correct 20 ms 2504 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3128 KB Output is correct
2 Correct 125 ms 7448 KB Output is correct
3 Runtime error 368 ms 18136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 18336 KB Output is correct
2 Correct 368 ms 22480 KB Output is correct
3 Correct 266 ms 23256 KB Output is correct
4 Correct 248 ms 24016 KB Output is correct
5 Correct 281 ms 24016 KB Output is correct
6 Correct 377 ms 26832 KB Output is correct
7 Correct 359 ms 27840 KB Output is correct
8 Correct 389 ms 31504 KB Output is correct
9 Correct 226 ms 31504 KB Output is correct
10 Correct 280 ms 31504 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Partially correct 297 ms 31504 KB Output is partially correct - 772365 bits used
2 Partially correct 382 ms 31504 KB Output is partially correct - 742095 bits used
3 Partially correct 339 ms 31504 KB Output is partially correct - 712470 bits used
4 Partially correct 383 ms 31504 KB Output is partially correct - 712005 bits used
5 Partially correct 330 ms 31552 KB Output is partially correct - 710610 bits used
6 Partially correct 371 ms 31552 KB Output is partially correct - 712155 bits used
7 Partially correct 408 ms 31552 KB Output is partially correct - 711090 bits used
8 Partially correct 327 ms 31672 KB Output is partially correct - 713340 bits used
9 Partially correct 362 ms 31672 KB Output is partially correct - 712830 bits used
10 Partially correct 507 ms 33992 KB Output is partially correct - 1117620 bits used