Submission #465590

#	Time	Username	Problem	Language	Result	Execution time	Memory
465590		Antekb	Tram (CEOI13_tram)	C++14	10 / 100	174 ms	13436 KiB

tram

#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){
	/*auto it=S.find(r1);
	assert(it!=S.end());
	it=next(it);
	assert(it!=S.end() && *it==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};
	}
	//assert(r1+1!=r2);
	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){
	//cout<<"b"<<endl;
	int r2=*S.upper_bound(x);
	int r1=-(*Sc.upper_bound(-x));
	//cout<<r1<<" "<<r2<<endl;
	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){
	//cout<<"!!!"<<endl;
	//cout<<x<<endl;
	//for(int i:S)cout<<i<<" ";
	//	cout<<"\n";
	//for(auto i:Q)cout<<"( "<<i.st.st<<" "<<i.st.nd<<" "<<i.nd.st<<" "<<i.nd.nd<<") ";
	//	cout<<"\n";
	//cout<<x<<endl;
	int r2=(*S.upper_bound(x));
	//cout<<r2<<endl;
	int r1=-(*Sc.upper_bound(-x));
	//cout<<r1<<"\n";
	//if(x==2)return;
	pair<int, int> a=opt(r1, r2);
	pair<int, int> b=dist(r1, r2, a);
	//cout<<r1<<" "<<r2<<"a"<<endl;
	//cout<<"a"<<endl;
	//for(auto i:Q)cout<<"( "<<i.st.st<<" "<<i.st.nd<<" "<<i.nd.st<<" "<<i.nd.nd<<") ";
	//cout<<endl;
	Q.erase(Q.find({b, a}));
	//cout<<"a"<<endl;
	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});
	}
	//cout<<"a"<<endl;
		
		S.insert(x);
		Sc.insert(-x);
}
void flip(int x, int y){
	//cout<<x<<" "<<y<<endl;
	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);
	//cout<<x<<" "<<y<<endl;
	czy[x][y]^=1;
	if(czy[x][0]|| czy[x][1])dodaj(x);
	//cout<<x<<" "<<y<<endl;
	if(czy[x][0] ^ czy[x][1])S2.insert(x);
	if(!czy[x][0] && !czy[x][1])S0.insert(x);
	//cout<<x<<" "<<y<<endl;
}
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 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20