oj.uz

Submission #280523

# Submission time Handle Problem Language Result Execution time Memory
280523 2020-08-22T21:43:01 Z amiratou Last supper (IOI12_supper) C++14
43 / 100
 366 ms 26432 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
typedef pair<int,int> ii;
const int INF = (int)(1e9);

vector<int> vec[100005];
int occ[100005];
set<ii,greater<ii> > myset;
int pos[100005],in[100005];

void ComputeAdvice(int *C, int N, int K, int M) {
	int l=31-__builtin_clz(K+1)+1;
	for (int i = 0; i < N; ++i)
	{
		pos[i]=i;
		occ[i]=sz(vec[C[i]]);
		vec[C[i]].push_back(i);
	}
	for (int i = 0; i < K; ++i){
		in[i]=1;
		if(!sz(vec[i]))myset.insert({INF,i});
		else myset.insert({vec[i][0],i});
	}
	vector<int> code;
	for (int i = 0; i < N; ++i)
	{
		if(in[C[i]]){
			myset.erase({i,C[i]});
			if((occ[i]+1)<sz(vec[C[i]]))myset.insert({vec[C[i]][occ[i]+1],C[i]});
			else myset.insert({INF,C[i]});
		}
		else{
			ii h=*myset.begin();
			myset.erase(myset.begin());
			assert(in[h.se]==1);
			code.push_back(pos[h.se]);
			in[h.se]=0,in[C[i]]=1;
			if((occ[i]+1)<sz(vec[C[i]]))myset.insert({vec[C[i]][occ[i]+1],C[i]});
			else myset.insert({INF,C[i]});
			pos[C[i]]=pos[h.se];
		}
		assert(sz(myset)==K);
	}
	for(auto it:code){
		for (int i = 0; i < l; ++i)
			WriteAdvice(((it>>i)&1));
	}
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
typedef pair<int,int> ii;
const int INF = (int)(1e9);

int tab[100005],here[100005];

void Assist(unsigned char *A, int N, int K, int R) {
	int l=31-__builtin_clz(K+1)+1;
	for (int i = 0; i < K; ++i)
		tab[i]=i,here[i]=1;
	assert(!(R%l));
	vector<int> vec;
	for (int i = 0; i < R; i+=l)
	{
		int nb=0;
		for (int j = 0; j < l; ++j)
			if(A[i+j]==1)nb+=(1<<j);
		vec.push_back(nb);
	}
	int idx=0;
	for (int i = 0; i < N; ++i)
	{
		int h=GetRequest();
		if(!here[h]){
			assert(idx<sz(vec));
			here[tab[vec[idx]]]=0;
			here[h]=1;
			PutBack(tab[vec[idx]]);
			tab[vec[idx]]=h;
			idx++;
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5376 KB Output is correct
2 Correct 2 ms 5376 KB Output is correct
3 Correct 4 ms 5632 KB Output is correct
4 Correct 6 ms 5632 KB Output is correct
5 Correct 7 ms 5888 KB Output is correct
6 Correct 11 ms 6144 KB Output is correct
7 Correct 7 ms 5888 KB Output is correct
8 Correct 13 ms 6400 KB Output is correct
9 Correct 15 ms 6144 KB Output is correct
10 Correct 12 ms 6208 KB Output is correct
11 Correct 12 ms 6144 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6912 KB Output is correct
2 Correct 104 ms 11336 KB Output is correct
3 Correct 303 ms 25112 KB Output is correct
4 Correct 198 ms 18760 KB Output is correct
5 Correct 282 ms 20496 KB Output is correct
6 Correct 307 ms 21160 KB Output is correct
7 Correct 275 ms 21512 KB Output is correct
8 Correct 281 ms 23312 KB Output is correct
9 Correct 155 ms 14856 KB Output is correct
10 Correct 276 ms 21896 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 18624 KB Output is correct
2 Correct 261 ms 21976 KB Output is correct
3 Correct 263 ms 21624 KB Output is correct
4 Correct 258 ms 20976 KB Output is correct
5 Correct 223 ms 18168 KB Output is correct
6 Correct 263 ms 21624 KB Output is correct
7 Correct 260 ms 21376 KB Output is correct
8 Correct 329 ms 26432 KB Output is correct
9 Correct 177 ms 17448 KB Output is correct
10 Correct 261 ms 21616 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5888 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 Correct 275 ms 21584 KB Output is partially correct - 772365 bits used
2 Correct 284 ms 21608 KB Output is partially correct - 742095 bits used
3 Correct 271 ms 21880 KB Output is partially correct - 712470 bits used
4 Correct 278 ms 21632 KB Output is partially correct - 712005 bits used
5 Correct 265 ms 21624 KB Output is partially correct - 710610 bits used
6 Correct 270 ms 21624 KB Output is partially correct - 712155 bits used
7 Correct 270 ms 21632 KB Output is partially correct - 711090 bits used
8 Correct 293 ms 21616 KB Output is partially correct - 713340 bits used
9 Correct 272 ms 21624 KB Output is partially correct - 712830 bits used
10 Correct 366 ms 26256 KB Output is partially correct - 1117620 bits used