제출 #117507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117507		evpipis	전차 (CEOI13_tram)	C++17	0 / 100	385 ms	4460 KiB

tram

#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);
      |             ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20