#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int len = 150005;
const ll inf = 1e15;
ll dis[len], hel[len][2];
ii cell[len], out[len];
int vis[len][2], n, m, k, lef[len], rig[len];
ll comp(int x1, int y1, int x2, int y2){
return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
void upd(int x){
lef[x] = rig[x] = -1;
for (int i = x*k; i < min(n, x*k+k); i++){
hel[i][0] = hel[i][1] = inf;
if (vis[i][0] || vis[i][1])
rig[x] = i;
if ((vis[i][0] || vis[i][1]) && (lef[x] == -1))
lef[x] = i;
}
dis[x] = -1;
int ls = rig[x];
for (int i = rig[x]-1; i > lef[x]; i--){
if (vis[i][0] || vis[i][1])
ls = i;
for (int l = 0; l < 2; l++){
if (vis[ls][0])
hel[i][l] = min(hel[i][l], comp(i, l, ls, 0));
if (vis[ls][1])
hel[i][l] = min(hel[i][l], comp(i, l, ls, 1));
}
}
ls = lef[x];
for (int i = lef[x]+1; i < rig[x]; i++){
if (vis[i][0] || vis[i][1])
ls = i;
for (int l = 0; l < 2; l++){
if (vis[ls][0])
hel[i][l] = min(hel[i][l], comp(i, l, ls, 0));
if (vis[ls][1])
hel[i][l] = min(hel[i][l], comp(i, l, ls, 1));
if (hel[i][l] > dis[x]){
dis[x] = hel[i][l];
cell[x] = mp(i, l);
}
}
}
}
int main(){
scanf("%d %d", &n, &m);
k = sqrt(n);
for (int i = 0; i*k < n; i++){
dis[i] = inf; // long long dis;
cell[i] = mp(0, 0);
lef[i] = rig[i] = -1;
}
for (int d = 1; d <= m; d++){
//for (int i = 0; i*k < n; i++)
// printf("[%d, %d], lef = %d, rig = %d, dis = %lld, cell = (%d, %d)\n", i*k+1, min(n, i*k+k)-1+1, lef[i]+1, rig[i]+1, dis[i], cell[i].fi+1, cell[i].se+1);
char tp;
int x;
scanf(" %c", &tp);
if (tp == 'E'){
ll mx = 0;
ii cur = mp(0, 0);
int ls = -1, fr = -1;
for (int i = 0; i*k < n; i++){
if (lef[i] == -1)
continue;
if (fr == -1)
fr = lef[i];
if (ls == -1){
if (dis[i] > mx){ // after previous
mx = dis[i];
cur = cell[i];
}
ls = rig[i];
continue;
}
int mid1 = (ls+lef[i])/2, mid2 = (ls+lef[i]+1)/2;
for (int j = mid1; j <= mid2; j++){
for (int l = 0; l < 2; l++){
ll temp = inf;
if (vis[lef[i]][0])
temp = min(temp, comp(j, l, lef[i], 0));
if (vis[lef[i]][1])
temp = min(temp, comp(j, l, lef[i], 1));
if (vis[ls][0])
temp = min(temp, comp(j, l, ls, 0));
if (vis[ls][1])
temp = min(temp, comp(j, l, ls, 1));
if (temp > mx){
mx = temp;
cur = mp(j, l);
}
}
}
if (dis[i] > mx){
mx = dis[i];
cur = cell[i];
}
ls = rig[i];
}
if (fr == -1){
mx = inf;
cur = mp(0, 0);
}
else{
//printf("fr = %d, ls = %d\n", fr, ls);
for (int l = 1; l >= 0; l--){
ll temp = inf;
if (vis[fr][0])
temp = min(temp, comp(0, l, fr, 0));
if (vis[fr][1])
temp = min(temp, comp(0, l, fr, 1));
if (temp >= mx){
mx = temp;
cur = mp(0, l);
}
}
for (int l = 0; l < 2; l++){
ll temp = inf;
if (vis[ls][0])
temp = min(temp, comp(n-1, l, ls, 0));
if (vis[ls][1])
temp = min(temp, comp(n-1, l, ls, 1));
if (temp > mx){
mx = temp;
cur = mp(n-1, l);
}
//printf("n-1, %d = %lld\n", l, temp);
}
}
vis[cur.fi][cur.se] = 1;
out[d] = cur;
upd(cur.fi/k);
printf("%d %d\n", cur.fi+1, cur.se+1);
}
else{
scanf("%d", &x);
vis[out[x].fi][out[x].se] = 0;
upd(out[x].fi/k);
}
}
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | scanf(" %c", &tp);
| ~~~~~^~~~~~~~~~~~
tram.cpp:171:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
171 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
3948 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
3960 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
128 ms |
1132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
385 ms |
4460 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
