oj.uz

Submission #419931

# Submission time Handle Problem Language Result Execution time Memory
419931 2021-06-07T18:23:50 Z faresbasbs Last supper (IOI12_supper) C++14
34 / 100
 508 ms 28792 KB 
#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
multiset<pair<int,int>> ms;
int k,lg,pos[100001];
set<int> st[100001];

void rt(int num){
	for(int i = lg-1 ; i >= 0 ; i -= 1){
		if(num & (1<<i)){
			WriteAdvice(1);
		}else{
			WriteAdvice(0);
		}
	}
}

void ComputeAdvice(int *C , int n , int K , int M){
	k = K , lg = ceil(log2(k+1));
	for(int i = 0 ; i < n ; i += 1){
		st[C[i]].insert(i);
		st[i].insert(n);
	}
	for(int i = 0 ; i < k ; i += 1){
		pos[i] = i;
		ms.insert({*st[i].upper_bound(-1),i});
	}
	for(int i = 0 ; i < n ; i += 1){
		if(ms.find({i,C[i]}) != ms.end()){
			ms.erase({i,C[i]});
			ms.insert({*st[C[i]].upper_bound(i),C[i]});
			rt(k);
		}else{
			pair<int,int> bd = *(--ms.end());
			ms.erase(bd);
			rt(pos[bd.second]);
			pos[C[i]] = pos[bd.second];
			ms.insert({*st[C[i]].upper_bound(i),C[i]});
		}
		/*cout << -1 << endl;
		for(auto j : ms){
			cout << j.first << " " << j.second << endl;
		}cout << endl << endl;*/
	}
}
#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
int lg2,val[100001];

void Assist(unsigned char *a , int n , int k , int R) {
	lg2 = ceil(log2(k+1));
	for(int i = 0 ; i < k ; i += 1){
		val[i] = i;
	}
	for(int i = 0 ; i < n ; i += 1){
		int num = 0 , num2 = GetRequest();
		for(int j = lg2*i ; j < lg2*(i+1) ; j += 1){
			num = 2*num;
			if(a[j] == 1){
				num += 1;
			}
		}
		if(num == k){
			continue;
		}
		PutBack(val[num]);
		val[num] = num2;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5232 KB Output is correct
2 Correct 3 ms 5240 KB Output is correct
3 Correct 6 ms 5372 KB Output is correct
4 Correct 8 ms 5784 KB Output is correct
5 Correct 8 ms 5772 KB Output is correct
6 Correct 14 ms 6020 KB Output is correct
7 Correct 17 ms 6124 KB Output is correct
8 Correct 17 ms 6240 KB Output is correct
9 Correct 18 ms 6148 KB Output is correct
10 Correct 19 ms 6268 KB Output is correct
11 Correct 21 ms 6288 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7212 KB Output is correct
2 Correct 190 ms 15200 KB Output is correct
3 Correct 502 ms 28256 KB Output is correct
4 Correct 237 ms 20752 KB Output is correct
5 Correct 359 ms 23252 KB Output is correct
6 Correct 406 ms 25204 KB Output is correct
7 Correct 466 ms 26960 KB Output is correct
8 Correct 369 ms 24080 KB Output is correct
9 Correct 196 ms 19128 KB Output is correct
10 Correct 470 ms 27396 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 22920 KB Output is correct
2 Correct 455 ms 27344 KB Output is correct
3 Correct 456 ms 28396 KB Output is correct
4 Correct 458 ms 28336 KB Output is correct
5 Correct 458 ms 27964 KB Output is correct
6 Correct 457 ms 28548 KB Output is correct
7 Correct 482 ms 28392 KB Output is correct
8 Correct 445 ms 28548 KB Output is correct
9 Correct 443 ms 28456 KB Output is correct
10 Correct 463 ms 28792 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
8.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 27004 KB Output is partially correct - 1500000 bits used
2 Correct 489 ms 27088 KB Output is partially correct - 1500000 bits used
3 Correct 477 ms 27484 KB Output is partially correct - 1500000 bits used
4 Correct 460 ms 27772 KB Output is partially correct - 1500000 bits used
5 Correct 456 ms 27276 KB Output is partially correct - 1500000 bits used
6 Correct 457 ms 27296 KB Output is partially correct - 1500000 bits used
7 Correct 458 ms 27464 KB Output is partially correct - 1497585 bits used
8 Correct 508 ms 27192 KB Output is partially correct - 1500000 bits used
9 Correct 473 ms 27312 KB Output is partially correct - 1500000 bits used
10 Correct 446 ms 27692 KB Output is partially correct - 1500000 bits used