oj.uz

답안 #264689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
264689 2020-08-14T08:24:14 Z 송준혁(#5083) 전차 (CEOI13_tram) C++17
0 / 100
 34 ms 3460 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M;
int X[30303], Y[30303];
bool A[150505][2];
set<int> S;
priority_queue<pii> PQ;

int main(){
	char ch;
	scanf("%d %d", &N, &M);
	PQ.push(pii(3*N, -2));
	for (int m=1; m<=M; m++){
		scanf(" %c", &ch);
		if (ch == 'E'){
			int x, y;
			pii t;
			while (1){
				t=PQ.top();
				PQ.pop();
				x=(-t.se)/2, y=(-t.se)&1;
				if (A[x][y]) continue;
				if (t.fi == 2) break;
				auto it = S.lower_bound(x);
				if (it != S.end()){
					if (A[*it][0] && t.fi > 2*(*it-x)+y) continue;
					if (A[*it][1] && t.fi > 2*(*it-x)+1-y) continue;
				}
				if (it != S.begin()){
					--it;
					if (A[*it][0] && t.fi > 2*(x-*it)+y) continue;
					if (A[*it][1] && t.fi > 2*(x-*it)+1-y) continue;
				}
				break;
			}
			printf("%d %d\n", x, y+1);
			A[x][y] = true;
			X[m]=x, Y[m]=y;
			S.insert(x);
			auto it = S.upper_bound(x);
			if (it == S.end()){
				PQ.push(pii((N-x)*2+(!A[x][0])+(N==x), -2*N));
				PQ.push(pii((N-x)*2+(!A[x][1])+(N==x), -2*N-1));
			}
			else{
				int p=(*it+x)/2;
				PQ.push(pii(max(min((*it-p)*2+(!A[*it][0]), (p-x)*2+(!A[x][0])), 2), -2*p));
				PQ.push(pii(max(min((*it-p)*2+(!A[*it][1]), (p-x)*2+(!A[x][1])), 2), -2*p-1));
			}
			--it;
			if (it == S.begin()){
				PQ.push(pii((x-1)*2+(!A[x][0])+(1==x), -2));
				PQ.push(pii((x-1)*2+(!A[x][1])+(1==x), -3));
				continue;
			}
			--it;
			int p=(*it+x)/2;
			PQ.push(pii(max(min((p-*it)*2+(!A[*it][0]), (x-p)*2+(!A[x][0])), 2), -2*p));
			PQ.push(pii(max(min((p-*it)*2+(!A[*it][1]), (x-p)*2+(!A[x][1])), 2), -2*p-1));
		}
		else{
			int x, y;
			scanf("%d", &x);
			y=Y[x], x=X[x];
			A[x][y] = false;
			if (!A[x][!y]){
				S.erase(x);
				auto b = S.lower_bound(x);
				if (b == S.begin()){
					if (S.empty()){
						PQ.push(pii(3*N, -2));
						continue;
					}
					PQ.push(pii((*b-1)*2+(!A[*b][0])+(1==*b), -2));
					PQ.push(pii((*b-1)*2+(!A[*b][1])+(1==*b), -3));
					continue;
				}
				auto a = b; --a;
				if (b == S.end()){
					PQ.push(pii((N-*a)*2+(!A[*a][0])+(N==*a), -2*N));
					PQ.push(pii((N-*a)*2+(!A[*a][1])+(N==*a), -2*N-1));
					continue;
				}
				x=(*a+*b)/2;
				PQ.push(pii(max(min((*b-x)*2+(!A[*b][0]), (x-*a)*2+(!A[*a][0])),2), -2*x));
				PQ.push(pii(max(min((*b-x)*2+(!A[*b][1]), (x-*a)*2+(!A[*a][1])),2), -2*x-1));
			}
			else{
				auto it = S.upper_bound(x);
				if (it == S.end()){
					PQ.push(pii((N-x)*2+(!A[x][0])+(N==x), -2*N));
					PQ.push(pii((N-x)*2+(!A[x][1])+(N==x), -2*N-1));
				}
				else{
					int t=(*it+x)/2;
					PQ.push(pii(max(min((*it-t)*2+(!A[*it][0]), (t-x)*2+(!A[x][0])), 2), -2*t));
					PQ.push(pii(max(min((*it-t)*2+(!A[*it][1]), (t-x)*2+(!A[x][1])), 2), -2*t-1));
				}
				--it;
				if (it == S.begin()){
					PQ.push(pii((x-1)*2+(!A[x][0])+(1==x), -2));
					PQ.push(pii((x-1)*2+(!A[x][1])+(1==x), -3));
					continue;
				}
				--it;
				int t=(*it+x)/2;
				PQ.push(pii(max(min((t-*it)*2+(!A[*it][0]), (x-t)*2+(!A[x][0])), 2), -2*t));
				PQ.push(pii(max(min((t-*it)*2+(!A[*it][1]), (x-t)*2+(!A[x][1])), 2), -2*t-1));
			}
		}
	}
	return 0;
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   scanf(" %c", &ch);
      |   ~~~~~^~~~~~~~~~~~
tram.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 748 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 748 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 1768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 3460 KB Output is correct
2 Incorrect 27 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -