Submission #245127

#	Time	Username	Problem	Language	Result	Execution time	Memory
245127		TadijaSebez	Tram (CEOI13_tram)	C++11	100 / 100	151 ms	9964 KiB

tram

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=150050;
int dist[N][2];
bool active[N][2],has[N][2];
set<pair<int,pii>> pos;
void Cons(int x,int y,vector<int> pts){
	if(active[x][y])return;
	int dst=N*2;
	for(int i:pts){
		for(int j=0;j<2;j++){
			if(has[i][j]){
				dst=min(dst,x!=i?abs(x-i)*2+abs(y-j):abs(y-j)*2);
				//printf("(%i %i - %i) ",i,j,x!=i?abs(x-i)*2+abs(y-j):abs(y-j)*2);
			}
		}
	}
	dist[x][y]=dst;
	active[x][y]=1;
	//printf("Add %i %i %i : ",x,y,dst);for(int i:pts)printf("%i ",i);printf("\n");
	pos.insert({-dst,{x,y}});
}
void Del(int x,int y){
	if(active[x][y]){
		//printf("Del %i %i %i\n",x,y,dist[x][y]);
		pos.erase({-dist[x][y],{x,y}});
		active[x][y]=0;
	}
}
int X[N],Y[N],n,m;
set<int> idx;
void Rec(set<int>::iterator it,int mod){
	vector<int> cns,tke;
	if(it==idx.end()&&it==idx.begin()){
		cns={1};tke={};
	}else if(it==idx.end()){
		cns={n};tke={*prev(it)};
	}else if(it==idx.begin()){
		cns={1};tke={*it};
	}else{
		int mid=*it+*prev(it)>>1;
		if((*it+*prev(it))&1)cns={mid,mid+1};
		else cns={mid};
		tke={*it,*prev(it)};
	}
	if(mod==0||mod==2){
		for(int i:cns)Del(i,0),Del(i,1);
	}
	if(mod==1||mod==2){
		for(int i:cns)Cons(i,0,tke),Cons(i,1,tke);
	}
}
int main(){
	scanf("%i %i",&n,&m);
	Rec(idx.begin(),1);
	for(int i=1;i<=m;i++){
		char c;scanf("\n%c",&c);
		if(c=='E'){
			tie(X[i],Y[i])=pos.begin()->second;
			//cout<<pos.begin()->first<<" "<<pos.begin()->second.first<<" "<<pos.begin()->second.second<<"\n";
			printf("%i %i\n",X[i],Y[i]+1);
			Del(X[i],Y[i]);
			has[X[i]][Y[i]]=1;
			if(idx.count(X[i])){
				Rec(idx.find(X[i]),2);
				Rec(next(idx.find(X[i])),2);
			}else{
				Rec(idx.upper_bound(X[i]),0);
				idx.insert(X[i]);
				Rec(idx.find(X[i]),1);
				Rec(next(idx.find(X[i])),1);
			}
		}else{
			int p;scanf("%i",&p);
			has[X[p]][Y[p]]=0;
			if(!has[X[p]][Y[p]^1]){
				Rec(idx.find(X[p]),0);
				Rec(next(idx.find(X[p])),0);
				idx.erase(X[p]);
				auto it=idx.upper_bound(X[p]);
				Rec(it,1);
				if(it!=idx.begin())Rec(prev(it),2);
				if(it!=idx.end())Rec(next(it),2);
			}else{
				Rec(idx.find(X[p]),2);
				Rec(next(idx.find(X[p])),2);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

tram.cpp: In function 'void Rec(std::set<int>::iterator, int)':
tram.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid=*it+*prev(it)>>1;
      |           ~~~^~~~~~~~~~
tram.cpp: In function 'int main()':
tram.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%i %i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
tram.cpp:58:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   char c;scanf("\n%c",&c);
      |          ~~~~~^~~~~~~~~~~
tram.cpp:75:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |    int p;scanf("%i",&p);
      |          ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20