oj.uz

Submission #137453

# Submission time Handle Problem Language Result Execution time Memory
137453 2019-07-27T18:46:55 Z jangwonyoung Last supper (IOI12_supper) C++14
43 / 100
 168 ms 14056 KB 
#include "advisor.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int n,k;
int prv[100001];
int nxt[100001];
int c[200001];
int in[100001];
bool die[200001];
set<pair<int,int> >v;
void ComputeAdvice(int *C, int N, int K, int M) {
	n=N;k=K;
	for(int i=1; i<=n ;i++){
		c[k+i]=C[i-1]+1;
		prv[i]=n+k+1;
	}
	for(int i=1; i<=k ;i++) c[i]=i;
	for(int i=n+k; i>=1 ;i--){
		nxt[i]=prv[c[i]];
		if(i<=k) v.insert({nxt[i],i});
		prv[c[i]]=i;
		if(i<=k) in[i]=true;
	}
	for(int i=k+1; i<=n+k ;i++){
		if(!in[c[i]]){
			auto it=v.end();--it;
			die[it->se]=true;
			in[c[it->se]]=0;
			v.erase(it);
		}
		else{
			v.erase({i,in[c[i]]});
		}
		v.insert({nxt[i],i});
		in[c[i]]=i;
	}
	for(int i=1; i<=n+k ;i++){
		WriteAdvice(die[i]);
	}
}
#include "assistant.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int n,k;
bool s[200001];
set<pair<int,int> >bin[2];
void Assist(unsigned char *A, int N, int K, int R){
	n=N;k=K;
	for(int i=1; i<=n+k ;i++) s[i]=!A[i-1];
	for(int i=1; i<=k ;i++){
		bin[s[i]].insert({i,i});
	}
	for(int i=k+1; i<=n+k ;i++){
		int cur=GetRequest()+1;
		auto it=bin[1].lower_bound({cur,0});
		if(it==bin[1].end() || it->fi!=cur){
			it=bin[0].begin();
			PutBack(it->fi-1);
			int duh=it->se;
			bin[0].erase(it);
			bin[s[i]].insert({cur,duh});
		}
		else{
			auto tmp=*it;
			bin[1].erase(it);
			bin[s[i]].insert(tmp);
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 756 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Correct 6 ms 1016 KB Output is correct
4 Correct 12 ms 1052 KB Output is correct
5 Correct 7 ms 1008 KB Output is correct
6 Correct 9 ms 1104 KB Output is correct
7 Correct 9 ms 1008 KB Output is correct
8 Correct 9 ms 1264 KB Output is correct
9 Correct 8 ms 1264 KB Output is correct
10 Correct 10 ms 1332 KB Output is correct
11 Correct 9 ms 1264 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2032 KB Output is correct
2 Correct 65 ms 4848 KB Output is correct
3 Incorrect 168 ms 14056 KB Error - Putting back a color that is not on the scaffold
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 9968 KB Output is correct
2 Incorrect 167 ms 12016 KB Error - Putting back a color that is not on the scaffold
3 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1060 KB Output is correct
2 Correct 9 ms 1264 KB Output is correct
3 Correct 7 ms 1068 KB Output is correct
4 Correct 7 ms 1068 KB Output is correct
5 Correct 8 ms 1000 KB Output is correct
6 Correct 9 ms 1008 KB Output is correct
7 Correct 9 ms 1084 KB Output is correct
8 Correct 9 ms 1264 KB Output is correct
9 Correct 10 ms 1264 KB Output is correct
10 Correct 11 ms 1824 KB Output is correct

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 11248 KB Error - Putting back a color that is not on the scaffold
2 Incorrect 156 ms 11504 KB Error - Putting back a color that is not on the scaffold
3 Incorrect 163 ms 12152 KB Error - Putting back a color that is not on the scaffold
4 Incorrect 162 ms 12088 KB Error - Putting back a color that is not on the scaffold
5 Incorrect 161 ms 12016 KB Error - Putting back a color that is not on the scaffold
6 Incorrect 162 ms 12472 KB Error - Putting back a color that is not on the scaffold
7 Incorrect 160 ms 12272 KB Error - Putting back a color that is not on the scaffold
8 Incorrect 162 ms 12024 KB Error - Putting back a color that is not on the scaffold
9 Incorrect 163 ms 12016 KB Error - Putting back a color that is not on the scaffold
10 Incorrect 142 ms 12784 KB Error - Putting back a color that is not on the scaffold