oj.uz

Submission #171251

# Submission time Handle Problem Language Result Execution time Memory
171251 2019-12-28T05:07:38 Z dndhk Last supper (IOI12_supper) C++14
20 / 100
 431 ms 26832 KB 
#include "advisor.h"
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MAX_N = 100000;

vector<int> need[MAX_N+1];

bool chk[MAX_N+1];
priority_queue<pii> pq;
int t = 0;

void send(int x){
	for(int i=0; i<t; i++){
		WriteAdvice((x%2));
		x/=2;
	}
	return;
}

void ComputeAdvice(int *C, int N, int K, int M) {
	while((1<<t)-1<N+1){
		t++;
	}
	for(int i=0; i<N; i++)	need[i].pb(N);
	for(int i=N-1; i>=0; i--){
		//cout<<i<<" "<<C[i]<<endl;
		need[C[i]].pb(i);
	}
	for(int i=0; i<K; i++){
		pq.push(make_pair(need[i].back(), i));
		chk[i] = true;
	}
	for(int i=0; i<N; i++){
		int now = C[i];
		if(chk[now]){
			send((1<<t)-1);
		}else{
			pii p;
			while(1){
				p = pq.top(); pq.pop();
				if(need[p.second].empty() || need[p.second].back()!=p.first){
					continue;
				}
				break;
			}
			//cout<<i<<" "<<p.first<<" "<<p.second<<endl;
			send(p.second);
			chk[p.second] = false;
		}
		need[now].pop_back();
		pq.push(make_pair(need[now].back(), now));
		chk[now] = true;
	}
}

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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;


int tt;

void Assist(unsigned char *A, int N, int K, int R) {
	while((1<<tt)-1<N+1){
		tt++;
	}
	int idx = 0;
	for(int i=0; i<N; i++){
		int req = GetRequest();
		int now = 0;
		for(int k=0; k<tt; k++){
			now = now + (int)A[idx]*(1<<k);
			idx++;
		}
		if(now==(1<<tt)-1){
			continue;
		}else{
			PutBack(now);
		}
	}

}

Compilation message

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:33:7: warning: unused variable 'req' [-Wunused-variable]
   int req = GetRequest();
       ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5456 KB Output is correct
2 Correct 7 ms 5304 KB Output is correct
3 Correct 9 ms 5616 KB Output is correct
4 Correct 15 ms 5880 KB Output is correct
5 Correct 25 ms 6128 KB Output is correct
6 Correct 23 ms 6272 KB Output is correct
7 Correct 22 ms 6384 KB Output is correct
8 Correct 23 ms 6384 KB Output is correct
9 Correct 23 ms 6128 KB Output is correct
10 Correct 22 ms 6384 KB Output is correct
11 Correct 22 ms 6392 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7352 KB Output is correct
2 Correct 189 ms 15760 KB Output is correct
3 Correct 425 ms 26632 KB Output is correct
4 Correct 420 ms 25448 KB Output is correct
5 Correct 423 ms 25832 KB Output is correct
6 Correct 421 ms 26008 KB Output is correct
7 Correct 410 ms 26576 KB Output is correct
8 Correct 366 ms 23064 KB Output is correct
9 Correct 388 ms 26472 KB Output is correct
10 Correct 425 ms 26832 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 21680 KB Output is correct
2 Incorrect 81 ms 17888 KB Error - advice is too long
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
3.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 25456 KB Output is partially correct - 1700000 bits used
2 Correct 414 ms 25480 KB Output is partially correct - 1700000 bits used
3 Correct 421 ms 25712 KB Output is partially correct - 1700000 bits used
4 Correct 415 ms 25632 KB Output is partially correct - 1700000 bits used
5 Correct 431 ms 25568 KB Output is partially correct - 1700000 bits used
6 Correct 423 ms 25648 KB Output is partially correct - 1700000 bits used
7 Correct 409 ms 25632 KB Output is partially correct - 1697263 bits used
8 Correct 427 ms 25568 KB Output is partially correct - 1700000 bits used
9 Correct 410 ms 25704 KB Output is partially correct - 1700000 bits used
10 Correct 420 ms 24968 KB Output is partially correct - 1700000 bits used