| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 274800 |
2020-08-19T15:56:02 Z |
arnold518 |
Tram (CEOI13_tram) |
C++14 |
|
1000 ms |
876 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
const int MAXM = 3e4;
int N, M, A[MAXN+10];
pii ans[MAXN+10];
set<int> S1, S2;
ll dist(ll x1, ll y1, ll x2, ll y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main()
{
scanf("%d%d", &N, &M);
for(int i=1; i<=M; i++)
{
char c;
scanf(" %c", &c);
if(c=='E') A[i]=-1;
else scanf("%d", &A[i]);
}
for(int i=1; i<=M; i++)
{
if(A[i]==-1)
{
ll val=-1; int y, x;
map<int, int> M;
for(auto it : S1) M[it]+=1;
for(auto it : S2) M[it]+=2;
if(M.empty())
{
y=1; x=1;
ans[i]={x, y};
if(y==1) S1.insert(x);
else S2.insert(x);
printf("%d %d\n", x, y);
continue;
}
for(auto it=M.begin(); next(it)!=M.end(); it++)
{
auto jt=next(it);
int x1=it->first, x2=jt->first;
int y1=it->second, y2=jt->second;
if(y1==3) y1=1; if(y2==3) y2=1;
if(y1==y2)
{
int nx=(x1+x2)/2, ny=1;
ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
else
{
int nx=(x1+x2)/2, ny=1;
ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
nx=(x1+x2)/2+1, ny=1;
now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
}
for(auto it=M.begin(); next(it)!=M.end(); it++)
{
auto jt=next(it);
int x1=it->first, x2=jt->first;
int y1=it->second, y2=jt->second;
if(y1==3) y1=2; if(y2==3) y2=2;
if(y1==y2)
{
int nx=(x1+x2)/2, ny=2;
ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
else
{
int nx=(x1+x2)/2, ny=2;
ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
nx=(x1+x2)/2+1, ny=2;
now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
}
{
int x1=M.begin()->first, y1=M.begin()->second;
if(y1==3) y1=1;
int nx=1, ny=1;
ll now=dist(nx, ny, x1, y1);
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
{
int x1=M.begin()->first, y1=M.begin()->second;
if(y1==3) y1=2;
int nx=1, ny=2;
ll now=dist(nx, ny, x1, y1);
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
{
int x1=(--M.end())->first, y1=(--M.end())->second;
if(y1==3) y1=1;
int nx=N, ny=1;
ll now=dist(nx, ny, x1, y1);
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
{
int x1=(--M.end())->first, y1=(--M.end())->second;
if(y1==3) y1=2;
int nx=N, ny=2;
ll now=dist(nx, ny, x1, y1);
if(val<now) val=now, x=nx, y=ny;
else if(val==now)
{
if(nx<x) x=nx, y=ny;
else if(nx==x && ny<y) y=ny;
}
}
ans[i]={x, y};
if(y==1) S1.insert(x);
else S2.insert(x);
printf("%d %d\n", x, y);
}
else
{
int x=ans[A[i]].first, y=ans[A[i]].second;
if(y==1) S1.erase(x);
else S2.erase(x);
}
}
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:55:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
55 | if(y1==3) y1=1; if(y2==3) y2=1;
| ^~
tram.cpp:55:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
55 | if(y1==3) y1=1; if(y2==3) y2=1;
| ^~
tram.cpp:93:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
93 | if(y1==3) y1=2; if(y2==3) y2=2;
| ^~
tram.cpp:93:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
93 | if(y1==3) y1=2; if(y2==3) y2=2;
| ^~
tram.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
22 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
26 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
tram.cpp:28:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | else scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
492 KB |
Output is correct |
| 2 |
Correct |
9 ms |
364 KB |
Output is correct |
| 3 |
Correct |
33 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
540 KB |
Output is correct |
| 2 |
Correct |
10 ms |
408 KB |
Output is correct |
| 3 |
Correct |
30 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
492 KB |
Output is correct |
| 2 |
Correct |
10 ms |
364 KB |
Output is correct |
| 3 |
Correct |
34 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
620 KB |
Output is correct |
| 2 |
Correct |
10 ms |
364 KB |
Output is correct |
| 3 |
Correct |
29 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1035 ms |
836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
