oj.uz

Submission #171249

# Submission time Handle Problem Language Result Execution time Memory
171249 2019-12-28T05:06:50 Z dndhk Last supper (IOI12_supper) C++14
0 / 100
 441 ms 25664 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=1; 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5304 KB Output is correct
2 Correct 7 ms 5456 KB Output is correct
3 Correct 9 ms 5560 KB Output is correct
4 Runtime error 9 ms 5468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7400 KB Output is correct
2 Runtime error 24 ms 9512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 21624 KB Output is correct
2 Incorrect 86 ms 17896 KB Error - advice is too long
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 430 ms 25496 KB Output isn't correct - not an optimal way
2 Correct 422 ms 25400 KB Output is partially correct - 1700000 bits used
3 Correct 431 ms 25664 KB Output is partially correct - 1700000 bits used
4 Runtime error 48 ms 12608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 430 ms 25616 KB Output is partially correct - 1700000 bits used
6 Runtime error 50 ms 12540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 441 ms 25648 KB Output is partially correct - 1697263 bits used
8 Correct 417 ms 25576 KB Output is partially correct - 1700000 bits used
9 Runtime error 49 ms 12452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 438 ms 25000 KB Output is partially correct - 1700000 bits used