Submission #465582

#	Time	Username	Problem	Language	Result	Execution time	Memory
465582		Antekb	Tram (CEOI13_tram)	C++14	10 / 100	148 ms	12100 KiB

tram

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=150005;
set<int> S, S2, S0;
int czy[N][2];
int n;
set<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){
	auto it=S.upper_bound(x);
	//assert(it!=S.end() && it!=S.begin());
	int r2=*it;
	it=prev(it);
	//assert(*it==x && it!=S.begin());
	it=prev(it);
	//assert(it!=S.end());
	int r1=*it;
	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));
}
void dodaj(int x){
	auto it=S.upper_bound(x);
	//assert(it!=S.end() && it!=S.begin());
	int r2=*it;
	it=prev(it);
	//assert(it!=S.end());
	int r1=*it;
	if(r1!=x-1){
		pair<int, int> a=opt(r1, x);
		pair<int, int> b=dist(r1, x, a);
		Q.insert({b, a});
	}
	if(r2!=x+1){
		pair<int, int> a=opt(x, r2);
		pair<int, int> b=dist(x, r2, a);
		Q.insert({b, a});
	}
		pair<int, int> a=opt(r1, r2);
		pair<int, int> b=dist(r1, r2, a);
		Q.erase(Q.find({b, a}));
		S.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);
	Q.insert({dist(0, n+1, opt(0, n+1)), opt(0, n+1)});
	for(int i=1; i<=q; i++){
		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