oj.uz

Submission #393658

# Submission time Handle Problem Language Result Execution time Memory
393658 2021-04-24T08:02:15 Z Hazem Last supper (IOI12_supper) C++14
34 / 100
 607 ms 34916 KB 
#include <bits/stdc++.h>
#include "advisor.h"
#define S second

using namespace std;

void appendint(int x,int len){
	
	//printf("%d\n",x);
	for(int i=0;i<=len;i++)
		WriteAdvice(char(((1<<i)&x)>0));
}

const int N1 = 2e5+100;

int nxt[N1],last[N1];
vector<int>freq[N1];
map<int,int>pos;

void ComputeAdvice(int *C, int N, int K, int M) {

    int len = 0;
    for(int i=1;;i++){
		if((1<<i)>K)break;
		len = i;
	}
	
	int n = N;
	for(int i=0;i<n;i++)
		freq[C[i]].push_back(i);
	
	for(int i=0;i<n;i++)
		freq[i].push_back(n+100);
		
	set<pair<int,int>>st;
	set<int>st1;
	for(int i=0;i<K;i++)
		st.insert({freq[i][0],i}),st1.insert(i),pos[i] = i;
	
	for(int i=0;i<n;i++){
		
		if(st1.find(C[i])!=st1.end()){
			appendint(0,len);
      st.erase({i,C[i]});
      int nxt = upper_bound(freq[C[i]].begin(),freq[C[i]].end(),i)-freq[C[i]].begin();
			nxt = freq[C[i]][nxt];
      st.insert({nxt,C[i]});
    }
		
		else {
			
			auto it = st.rbegin();
			int val = (*it).S;
			
			st1.erase(val);
			st1.insert(C[i]);
			pos[C[i]] = pos[val];
			
			appendint(pos[val]+1,len);
			
			st.erase(*it);
			int nxt = upper_bound(freq[C[i]].begin(),freq[C[i]].end(),i)-freq[C[i]].begin();
			nxt = freq[C[i]][nxt];
			
			st.insert({nxt,C[i]});
		} 		
	}
}

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

int a[2000000],vals[2000000];

int get(int idx,int len){
	
	int ret = 0;
	for(int i=idx;i<=idx+len;i++)
		ret += (1<<(i-idx))*a[i];
	
	return ret;
}

void Assist(unsigned char *A, int N, int K, int R) {
	
  // printf("%d\n",R);
	// for(int i=0;i<R;i++)
	// 	cout<<A[i];
		
	int len = 0;
	for(int i=0;;i++){
		if((1<<i)>K)break;
		len = i;
	}
	
	for(int i=0;i<K;i++)
		vals[i] = i;
		
	for(int i=0;i<R;i++)
		a[i] = A[i];
	
	int n = N;
	for(int i=0;i<n;i++){
		
		int val = GetRequest();
		int val1 = get(i*(len+1),len);
		
		if(!val1)continue;
		
		PutBack(vals[val1-1]);
		vals[val1-1] = val;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5236 KB Output is correct
2 Correct 3 ms 5244 KB Output is correct
3 Correct 8 ms 5640 KB Output is correct
4 Correct 9 ms 5564 KB Output is correct
5 Correct 10 ms 5784 KB Output is correct
6 Correct 16 ms 6096 KB Output is correct
7 Correct 17 ms 5984 KB Output is correct
8 Correct 23 ms 6524 KB Output is correct
9 Correct 22 ms 6236 KB Output is correct
10 Correct 22 ms 6460 KB Output is correct
11 Correct 22 ms 6412 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7420 KB Output is correct
2 Correct 196 ms 15712 KB Output is correct
3 Correct 607 ms 34916 KB Output is correct
4 Correct 283 ms 20724 KB Output is correct
5 Correct 420 ms 24500 KB Output is correct
6 Correct 465 ms 28096 KB Output is correct
7 Correct 523 ms 31672 KB Output is correct
8 Correct 498 ms 29696 KB Output is correct
9 Correct 195 ms 16100 KB Output is correct
10 Correct 539 ms 32992 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 25824 KB Output is correct
2 Correct 547 ms 32204 KB Output is correct
3 Correct 607 ms 32336 KB Output is correct
4 Correct 595 ms 32084 KB Output is correct
5 Correct 488 ms 30668 KB Output is correct
6 Correct 544 ms 32256 KB Output is correct
7 Correct 581 ms 32376 KB Output is correct
8 Correct 542 ms 33524 KB Output is correct
9 Correct 479 ms 31416 KB Output is correct
10 Correct 561 ms 32424 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5620 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 547 ms 30556 KB Output is partially correct - 1500000 bits used
2 Correct 545 ms 30704 KB Output is partially correct - 1500000 bits used
3 Correct 535 ms 31124 KB Output is partially correct - 1500000 bits used
4 Correct 550 ms 31148 KB Output is partially correct - 1500000 bits used
5 Correct 568 ms 31236 KB Output is partially correct - 1500000 bits used
6 Correct 559 ms 31140 KB Output is partially correct - 1500000 bits used
7 Correct 539 ms 31080 KB Output is partially correct - 1497585 bits used
8 Correct 583 ms 31064 KB Output is partially correct - 1500000 bits used
9 Correct 590 ms 31036 KB Output is partially correct - 1500000 bits used
10 Correct 593 ms 32340 KB Output is partially correct - 1500000 bits used