oj.uz

Submission #245127

# Submission time Handle Problem Language Result Execution time Memory
245127 2020-07-05T14:36:15 Z TadijaSebez Tram (CEOI13_tram) C++11
100 / 100
 151 ms 9964 KB 
#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

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.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 6 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 6 ms 544 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2412 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 6 ms 2284 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2412 KB Output is correct
2 Correct 6 ms 436 KB Output is correct
3 Correct 5 ms 2284 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 3648 KB Output is correct
2 Correct 122 ms 876 KB Output is correct
3 Correct 151 ms 2540 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9964 KB Output is correct
2 Correct 93 ms 996 KB Output is correct
3 Correct 128 ms 4588 KB Output is correct