제출 #117507

#제출 시각아이디문제언어결과실행 시간메모리
117507evpipis전차 (CEOI13_tram)C++17
0 / 100
385 ms4460 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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);
      |             ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...