oj.uz

답안 #465597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465597 2021-08-16T13:40:42 Z Antekb 전차 (CEOI13_tram) C++14
100 / 100
 161 ms 13532 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=150005;
set<int> S, S2, S0, Sc;
int czy[N][2];
int n;
multiset<pair<pair<int, int>, pair<int, int> > > Q;
pair<int, int> opt(int r1, int r2){
	if(r1==0 && r2==n+1){
		return {1, 0};
	}
	if(r1==0){
		if(czy[r2][1])return {1, 0};
		else return {1, 1};
	}
	if(r2==n+1){
		if(czy[r1][1])return {n, 0};
		else return {n, 1};
	}
	if(czy[r1][1] && czy[r1][0] && ((r1+r2)&1) && (czy[r2][0]^czy[r2][1])){
		return {(r1+r2+1)/2, czy[r2][0]};
	}
	if((!czy[r1][1] && ((r1+r2)&1)) || (!czy[r2][1] && !czy[r1][1]))return {(r1+r2)/2, 1};
	return {(r1+r2)/2, 0};
}
pair<int, int> dist(int r1, int r2, pair<int, int> poz){
	pair<int, int> ans;
	pair<int, int> x={N, N}, y={N, N};
	if(r1){
		x.st=poz.st-r1;
		x.nd=!czy[r1][poz.nd];
	}
	if(r2!=n+1){
		y.st=r2-poz.st;
		y.nd=!czy[r2][poz.nd];
	}
	x = min(x, y);
	x.st=-x.st;
	x.nd=-x.nd;
	//cout<<-x.st<<" "<<-x.nd<<" "<<poz.st<<" "<<poz.nd<<" "<<r1<<" "<<r2<<endl;
	return x;
}

void usun(int x){
	int r2=*S.upper_bound(x);
	int r1=-(*Sc.upper_bound(-x));
	if(r1!=x-1){
		pair<int, int> a=opt(r1, x);
		pair<int, int> b=dist(r1, x, a);
		Q.erase(Q.find({b, a}));
	}
	if(r2!=x+1){
		pair<int, int> a=opt(x, r2);
		pair<int, int> b=dist(x, r2, a);
		Q.erase(Q.find({b, a}));
	}
	pair<int, int> a=opt(r1, r2);
	pair<int, int> b=dist(r1, r2, a);
	Q.insert({b, a});
	S.erase(S.find(x));
	Sc.erase(Sc.find(-x));
}
void dodaj(int x){
	int r2=(*S.upper_bound(x));
	int r1=-(*Sc.upper_bound(-x));
	pair<int, int> a=opt(r1, r2);
	pair<int, int> b=dist(r1, r2, a);
	Q.erase(Q.find({b, a}));
	if(r1!=x-1){
		a=opt(r1, x);
		b=dist(r1, x, a);
		Q.insert({b, a});
	}
	if(r2!=x+1){
		a=opt(x, r2);
		b=dist(x, r2, a);
		Q.insert({b, a});
	}
	S.insert(x);
	Sc.insert(-x);
}
void flip(int x, int y){
	if(!czy[x][0] && !czy[x][1])S0.erase(S0.find(x));
	if(czy[x][0] ^ czy[x][1])S2.erase(S2.find(x));
	if(czy[x][0] || czy[x][1])usun(x);
	czy[x][y]^=1;
	if(czy[x][0]|| czy[x][1])dodaj(x);
	if(czy[x][0] ^ czy[x][1])S2.insert(x);
	if(!czy[x][0] && !czy[x][1])S0.insert(x);
}
pair<int, int> co[N];
int main(){
	int q;
	cin>>n>>q;
	for(int i=1; i<=n; i++)S0.insert(i);
	S.insert(0);
	S.insert(n+1);
	Sc.insert(-n-1);
	Sc.insert(0);
	Q.insert({dist(0, n+1, opt(0, n+1)), opt(0, n+1)});
	srand(time(NULL));
	for(int i=1; i<=q; i++){
		//int x, y;
		//cin>>x>>y;
		//flip(x, y);
		//flip(1+rand()%n, rand()%2);
		//continue;
		char c;
		cin>>c;
		if(c=='E' && Q.size() && (*Q.begin()).st!=make_pair(-1, 0)){
			pair<int, int> poz=(*Q.begin()).nd;
			flip(poz.st, poz.nd);
			cout<<poz.st<<" "<<poz.nd+1<<"\n";
			co[i]=poz;
		}
		else if(c=='E'){
			int x=n+1;
			if(S0.size())x=*S0.begin();
			if(S2.size())x=min(x, *S2.begin());
			if(czy[x][0])flip(x, 1), co[i]={x, 1};
			else flip(x, 0), co[i]={x, 0};
			cout<<x<<" "<<co[i].nd+1<<"\n";
		}
		else{
			//cout<<"-\n";
			int a;
			cin>>a;
			flip(co[a].st, co[a].nd);
		}
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 5 ms 592 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 544 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 4 ms 460 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 8748 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 40 ms 8524 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 8752 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 45 ms 8516 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 2888 KB Output is correct
2 Correct 87 ms 800 KB Output is correct
3 Correct 82 ms 2744 KB Output is correct

Subtask #8
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 13532 KB Output is correct
2 Correct 66 ms 708 KB Output is correct
3 Correct 136 ms 10300 KB Output is correct