oj.uz

Submission #465572

# Submission time Handle Problem Language Result Execution time Memory
465572 2021-08-16T12:07:45 Z Antekb Tram (CEOI13_tram) C++14
10 / 100
 151 ms 12208 KB 
#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][0])return {0, 1};
		else return {1, 0};
	}
	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<<"\n";
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 6

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Runtime error 2 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Runtime error 2 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8612 KB Output is correct
2 Runtime error 2 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8592 KB Output is correct
2 Runtime error 2 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 2432 KB Output is correct
2 Runtime error 8 ms 716 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 12208 KB Output is correct
2 Runtime error 9 ms 716 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -