oj.uz

Submission #73869

# Submission time Handle Problem Language Result Execution time Memory
73869 2018-08-29T07:42:08 Z FLDutchman Last supper (IOI12_supper) C++14
43 / 100
 453 ms 24128 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);
	for(; 1<<NUM_BITS < K; NUM_BITS++);

	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;
	for(; 1<< nb < K; nb++);
 	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:27:2: note: in expansion of macro 'FOR'
  FOR(i,0,C.size()){
  ^~~
advisor.cpp:33: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 5 ms 860 KB Output is correct
2 Correct 6 ms 968 KB Output is correct
3 Correct 7 ms 1104 KB Output is correct
4 Correct 9 ms 1256 KB Output is correct
5 Correct 11 ms 1512 KB Output is correct
6 Correct 18 ms 1768 KB Output is correct
7 Correct 12 ms 1768 KB Output is correct
8 Correct 20 ms 1904 KB Output is correct
9 Correct 27 ms 1904 KB Output is correct
10 Correct 19 ms 1904 KB Output is correct
11 Correct 14 ms 1904 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2632 KB Output is correct
2 Correct 147 ms 5936 KB Output is correct
3 Correct 386 ms 16040 KB Output is correct
4 Correct 188 ms 16040 KB Output is correct
5 Correct 337 ms 16040 KB Output is correct
6 Correct 418 ms 16592 KB Output is correct
7 Correct 352 ms 18184 KB Output is correct
8 Correct 453 ms 19592 KB Output is correct
9 Correct 156 ms 19592 KB Output is correct
10 Correct 295 ms 21744 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 21744 KB Output is correct
2 Correct 294 ms 21744 KB Output is correct
3 Correct 392 ms 21744 KB Output is correct
4 Correct 333 ms 21744 KB Output is correct
5 Correct 286 ms 21744 KB Output is correct
6 Correct 312 ms 21888 KB Output is correct
7 Correct 308 ms 21888 KB Output is correct
8 Correct 435 ms 24128 KB Output is correct
9 Correct 204 ms 24128 KB Output is correct
10 Correct 290 ms 24128 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 24128 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 318 ms 24128 KB Output is partially correct - 772365 bits used
2 Partially correct 291 ms 24128 KB Output is partially correct - 742095 bits used
3 Partially correct 302 ms 24128 KB Output is partially correct - 712470 bits used
4 Partially correct 367 ms 24128 KB Output is partially correct - 712005 bits used
5 Partially correct 315 ms 24128 KB Output is partially correct - 710610 bits used
6 Partially correct 300 ms 24128 KB Output is partially correct - 712155 bits used
7 Partially correct 303 ms 24128 KB Output is partially correct - 711090 bits used
8 Partially correct 289 ms 24128 KB Output is partially correct - 713340 bits used
9 Partially correct 278 ms 24128 KB Output is partially correct - 712830 bits used
10 Partially correct 359 ms 24128 KB Output is partially correct - 1117620 bits used