Submission #117542

#	Time	Username	Problem	Language	Result	Execution time	Memory
117542		evpipis	Tram (CEOI13_tram)	C++17	100 / 100	408 ms	4332 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)*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 (stderr)

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

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