| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117542 |
2019-06-16T13:34:29 Z |
evpipis |
Tram (CEOI13_tram) |
C++17 |
|
408 ms |
4332 KB |
#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)*1LL*(x1-x2) + (y1-y2)*1LL*(y1-y2);
}
void upd(int x){
lef[x] = rig[x] = -1;
for (int i = x*k; i < min(n, x*k+k); i++){
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++){
hel[i][l] = inf;
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(){
/*if (1){
system("fc tram.out.1a mytram.out.1a.txt");
return 0;
}
freopen("tram.in.1a", "r", stdin);
freopen("mytram.out.1a.txt", "w", stdout);*/
scanf("%d %d", &n, &m);
k = sqrt(n);
for (int i = 0; i*k < n; i++)
upd(i);
//int flag = 0;
for (int d = 1; d <= m; d++){
/*if (flag){
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);
for (int i = 0; i < n; i++)
printf("%d: %d %d\n", i+1, vis[i][0], vis[i][1]);
flag = 0;
}*/
//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 = -1;
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){
if (dis[i] > mx){
mx = dis[i];
cur = cell[i];
}
ls = rig[i];
fr = lef[i];
continue;
}
int mid1 = (ls+lef[i])/2, mid2 = (ls+lef[i]+1)/2;
if (lef[i]-ls+1 <= 4)
mid1 = ls, mid2 = lef[i];
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);
//if (cur.fi == 10 && cur.se == 0)
// flag = 1;
}
else{
scanf("%d", &x);
vis[out[x].fi][out[x].se] = 0;
upd(out[x].fi/k);
}
}
//freopen("CON", "w", stdout);
//printf("hello\n");
//system("fc tram.in.1a mytram.out.1a.txt");
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
94 | scanf(" %c", &tp);
| ~~~~~^~~~~~~~~~~~
tram.cpp:189:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
189 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 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 |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
3948 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
8 ms |
2284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
3948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
11 ms |
2284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
34 ms |
748 KB |
Output is correct |
| 3 |
Correct |
140 ms |
1132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
408 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
32 ms |
748 KB |
Output is correct |
| 3 |
Correct |
213 ms |
4204 KB |
Output is correct |
