| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 264689 |
2020-08-14T08:24:14 Z |
송준혁(#5083) |
Tram (CEOI13_tram) |
C++17 |
|
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);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
1768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
