oj.uz

Submission #171254

# Submission time Handle Problem Language Result Execution time Memory
171254 2019-12-28T05:52:32 Z dndhk Last supper (IOI12_supper) C++14
100 / 100
 197 ms 25320 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 = 200000;

vector<int> need[MAX_N+1];

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

void ComputeAdvice(int *C, int N, int K, int M) {
	for(int i=0; i<N; i++)	need[i].pb(N);

	for(int i=N-1; i>=0; i--){
		need[C[i]].pb(i);
	}
	for(int i=0; i<K; i++){
		idx[i] = 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[idx[now]] = true;
			idx[now] = i+K;
		}else{
			pii p;
			while(1){
				p = pq.top(); pq.pop();
				if(need[p.second].empty() || need[p.second].back()!=p.first){
					continue;
				}
				break;
			}
			chk[p.second] = false;
		}
		need[now].pop_back();
		pq.push(make_pair(need[now].back(), now));
		idx[now] = i+K;
		chk[now] = true;
	}
	while(!pq.empty()){
		pii p = pq.top(); pq.pop();
		if(need[p.second].empty() || need[p.second].back()!=p.first){
			continue;
		}
		send[idx[p.second]] = true;
	}
	for(int i=0; i<N+K; i++){
		WriteAdvice(send[i]);
	}
}

#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;
const int MAX_N1 = 200000;

bool chk2[MAX_N1+1];

vector<int> vt;

void Assist(unsigned char *A, int N, int K, int R) {
	for(int i=0; i<K; i++){
		if(!A[i]){
			vt.pb(i);
		}else{
			chk2[i] = true;
		}
	}
	int idx = 0;
	for(int i=0; i<N; i++){
		int req = GetRequest();
		if(chk2[req]){
			chk2[req] = false;
		}else{
			PutBack(vt.back());
			vt.pop_back();
		}
		if(A[K+i]){
			chk2[req] = true;
		}else{
			vt.pb(req);
		}
	}
}

Compilation message

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:37:6: warning: unused variable 'idx' [-Wunused-variable]
  int idx = 0;
      ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9968 KB Output is correct
2 Correct 7 ms 9968 KB Output is correct
3 Correct 9 ms 10224 KB Output is correct
4 Correct 12 ms 10480 KB Output is correct
5 Correct 13 ms 10480 KB Output is correct
6 Correct 13 ms 10744 KB Output is correct
7 Correct 16 ms 10992 KB Output is correct
8 Correct 10 ms 10736 KB Output is correct
9 Correct 15 ms 10736 KB Output is correct
10 Correct 14 ms 10992 KB Output is correct
11 Correct 14 ms 10744 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11248 KB Output is correct
2 Correct 63 ms 16960 KB Output is correct
3 Correct 153 ms 22920 KB Output is correct
4 Correct 113 ms 21128 KB Output is correct
5 Correct 125 ms 21168 KB Output is correct
6 Correct 130 ms 21728 KB Output is correct
7 Correct 148 ms 22496 KB Output is correct
8 Correct 123 ms 20448 KB Output is correct
9 Correct 91 ms 22336 KB Output is correct
10 Correct 156 ms 22944 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 20200 KB Output is correct
2 Correct 149 ms 22552 KB Output is correct
3 Correct 152 ms 23984 KB Output is correct
4 Correct 139 ms 24032 KB Output is correct
5 Correct 130 ms 24544 KB Output is correct
6 Correct 149 ms 23960 KB Output is correct
7 Correct 160 ms 24056 KB Output is correct
8 Correct 140 ms 23272 KB Output is correct
9 Correct 135 ms 25320 KB Output is correct
10 Correct 156 ms 24024 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10480 KB Output is correct
2 Correct 13 ms 10736 KB Output is correct
3 Correct 12 ms 10736 KB Output is correct
4 Correct 12 ms 10736 KB Output is correct
5 Correct 12 ms 10736 KB Output is correct
6 Correct 13 ms 10736 KB Output is correct
7 Correct 15 ms 10736 KB Output is correct
8 Correct 13 ms 10944 KB Output is correct
9 Correct 13 ms 10736 KB Output is correct
10 Correct 15 ms 10992 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 22480 KB Output is correct - 120000 bits used
2 Correct 197 ms 22768 KB Output is correct - 122000 bits used
3 Correct 148 ms 22712 KB Output is correct - 125000 bits used
4 Correct 157 ms 22808 KB Output is correct - 125000 bits used
5 Correct 170 ms 22832 KB Output is correct - 125000 bits used
6 Correct 186 ms 22736 KB Output is correct - 125000 bits used
7 Correct 175 ms 22616 KB Output is correct - 124828 bits used
8 Correct 154 ms 22688 KB Output is correct - 124910 bits used
9 Correct 181 ms 22936 KB Output is correct - 125000 bits used
10 Correct 169 ms 21992 KB Output is correct - 125000 bits used