Submission #73869

#	Time	Username	Problem	Language	Result	Execution time	Memory
73869		FLDutchman	Last supper (IOI12_supper)	C++14	43 / 100	453 ms	24128 KiB

advisor

#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]);
		}
	}
}

assistant

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 35
• Subtask 5: 17 / 39