oj.uz

답안 #241776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241776 2020-06-25T13:05:52 Z kshitij_sodani 최후의 만찬 (IOI12_supper) C++17
100 / 100
 303 ms 66288 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

#include "advisor.h"
//void WriteAdvice(int x);
vector<int> ind[1000001];
int ans[2000001];
set<int> cur;
int prev2[2000001];
/*void WriteAdvice(int x){
	cout<<x<<endl;
}
*/
void ComputeAdvice(int c[], int n, int k, int m) {

	set<pair<int,int>> kk;
	for(int i=0;i<n;i++){
		ind[c[i]].pb(i);
	}
	for(int i=0;i<n;i++){
		ind[i].pb(n+1);
	}
	for(int i=0;i<k;i++){
		kk.insert({ind[i][0],i});
		prev2[i]=i;
		cur.insert(i);
	}

	for(int i=0;i<n;i++){
		if(cur.find(c[i])!=cur.end()){

			kk.erase({i,prev2[c[i]]});
			prev2[c[i]]=i+k;
			int j=upper_bound(ind[c[i]].begin(),ind[c[i]].end(),i)-ind[c[i]].begin();
			kk.insert({ind[c[i]][j],i+k});
			continue;
		}
		auto j=kk.end();
		j--;
		ans[(*j).b]=1;
		if((*j).b>=k){
			cur.erase(c[(*j).b-k]);
		}
		else{
			cur.erase((*j).b);
		}
		cur.insert(c[i]);
		kk.erase(j);
		int jj=upper_bound(ind[c[i]].begin(),ind[c[i]].end(),i)-ind[c[i]].begin();
		kk.insert({ind[c[i]][jj],i+k});
		prev2[c[i]]=i+k;
	}

	for(int i=0;i<n+k;i++){
		WriteAdvice(ans[i]);
	}

 //	WriteAdvice(0);
}
/*int main(){
	int cc[4];
	cc[0]=2;
	cc[1]=0;
	cc[2]=3;
	cc[3]=0;

	ComputeAdvice(cc,4,2,1000);
	return 0;
}
*/

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

#include "assistant.h"
set<int> cur3;
set<int> cur4;
int ind3=0;
int rr;
//void PutBack(int x);
//int GetRequest();
/*
int read(){
	int ans=0;

	for(int i=0;i<15;i++){
		if(aa[ind3+i]=='1'){
			ans+=(1<<i);
		}
	}
	ind3+=15;
	return ans;
}*/
/*int GetRequest(){
	int yy;
	cin>>yy;
	return yy;
}
void PutBack(int x){
	cout<<x<<":"<<endl;
}*/
void Assist(unsigned char aa[], int n, int k, int ro) {
/*	rr=ro;

	for(int i=0;i<ro;i++){
		aa[i]=A[i];
	}*/
	for(int i=0;i<k;i++){
		cur4.insert(i);
		if(aa[i]){
			cur3.insert(i);
		}
	//	cur3.insert(i);
	}

	int st=0;
	for (int i = 0; i < n; i++) {
		int req = GetRequest();
		if (cur4.find(req)==cur4.end()){
		/*	if(cur3.size()==0){
				return;
			}*/
		 	PutBack((*cur3.begin()));
		 	cur4.erase((*cur3.begin()));
		 	cur3.erase(cur3.begin());
		 	if(aa[i+k]){
		 		cur3.insert(req);
		 	}
		 	cur4.insert(req);
		}
		else{
			if(cur3.find(req)!=cur3.end()){
				cur3.erase(req);
			}
			if(aa[i+k]){
				cur3.insert(req);
			}
		}
	}

}

/*int main(){
	int cc[4];
	int nn;
	cin>>nn;
	unsigned char aa[nn];
	for(int i=0;i<nn;i++){
		cin>>aa[i];
	}

	Assist(aa,4,2,nn);
	return 0;
}

*/

Compilation message

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47616 KB Output is correct
2 Correct 25 ms 47504 KB Output is correct
3 Correct 25 ms 47872 KB Output is correct
4 Correct 27 ms 48112 KB Output is correct
5 Correct 30 ms 48128 KB Output is correct
6 Correct 31 ms 48128 KB Output is correct
7 Correct 28 ms 48384 KB Output is correct
8 Correct 34 ms 48640 KB Output is correct
9 Correct 32 ms 48384 KB Output is correct
10 Correct 31 ms 48504 KB Output is correct
11 Correct 31 ms 48384 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 49152 KB Output is correct
2 Correct 109 ms 54560 KB Output is correct
3 Correct 288 ms 66288 KB Output is correct
4 Correct 178 ms 59328 KB Output is correct
5 Correct 185 ms 59376 KB Output is correct
6 Correct 218 ms 60400 KB Output is correct
7 Correct 303 ms 63112 KB Output is correct
8 Correct 248 ms 62192 KB Output is correct
9 Correct 136 ms 60144 KB Output is correct
10 Correct 259 ms 65264 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 60864 KB Output is correct
2 Correct 249 ms 64184 KB Output is correct
3 Correct 254 ms 64240 KB Output is correct
4 Correct 253 ms 64240 KB Output is correct
5 Correct 233 ms 63472 KB Output is correct
6 Correct 291 ms 64240 KB Output is correct
7 Correct 253 ms 64248 KB Output is correct
8 Correct 245 ms 63984 KB Output is correct
9 Correct 215 ms 64240 KB Output is correct
10 Correct 257 ms 64240 KB Output is correct

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 48384 KB Output is correct
2 Correct 32 ms 48384 KB Output is correct
3 Correct 32 ms 48128 KB Output is correct
4 Correct 27 ms 48128 KB Output is correct
5 Correct 32 ms 48384 KB Output is correct
6 Correct 31 ms 48128 KB Output is correct
7 Correct 30 ms 48384 KB Output is correct
8 Correct 31 ms 48384 KB Output is correct
9 Correct 31 ms 48384 KB Output is correct
10 Correct 32 ms 48896 KB Output is correct

Subtask #5
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 63216 KB Output is correct - 120000 bits used
2 Correct 256 ms 63728 KB Output is correct - 122000 bits used
3 Correct 255 ms 64496 KB Output is correct - 125000 bits used
4 Correct 255 ms 64240 KB Output is correct - 125000 bits used
5 Correct 250 ms 64240 KB Output is correct - 125000 bits used
6 Correct 258 ms 64240 KB Output is correct - 125000 bits used
7 Correct 271 ms 64344 KB Output is correct - 124828 bits used
8 Correct 265 ms 64240 KB Output is correct - 124910 bits used
9 Correct 258 ms 64496 KB Output is correct - 125000 bits used
10 Correct 245 ms 64240 KB Output is correct - 125000 bits used