제출 #1041706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041706		vjudge1	Tenis (COI19_tenis)	C++17	51 / 100	74 ms	5728 KiB

tenis

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, q, p[N][3], ind[N][3], f[3];

bool check(int x){
    int it[3] = {n, n, n};
    int nit[3] = {ind[x][0], ind[x][1], ind[x][2]};
    int ite = 4 * n;
    while (ite > 0){
        for (int j = 0; j < 3; j ++){
            ite--;
            for (int i = it[j]; i >= nit[j]; i --){
                ite--;
                int ele = p[i][j];

                nit[0] = min(nit[0], ind[ele][0]);
                nit[1] = min(nit[1], ind[ele][1]);
                nit[2] = min(nit[2], ind[ele][2]);
            }
            it[j] = nit[j] - 1;
        }
    }

    return nit[0] == 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for (int j = 0; j < 3; j ++){
        for (int i = 1; i <= n; i ++){
            cin >> p[i][j];
            ind[p[i][j]][j] = i;
        }
    }

    for (int j = 0; j < 3; j ++){
        f[j] = 1;
        int l = 1;
        int r = n + 1;

        while (r - l > 1){
            int mid = (l + r) / 2;
            if (check(p[mid][j]))
                l = mid;
            else
                r = mid;
        }
        f[j] = l;
    }


    for (int i = 0; i < q; i ++){
        int t;
        cin >> t;

        if (t == 1){
            int x;
            cin >> x;
            if (q <= 10){
                cout << (check(x) ? "DA\n" : "NE\n");
            }
            else{
                if (ind[x][0] <= f[0] or ind[x][1] <= f[1] or ind[x][2] <= f[2])
                    cout << "DA\n";
                else
                    cout << "NE\n";
            }
        }
        else{
            int j, a, b;
            cin >> j >> a >> b;
            j--;
            swap(p[ind[a][j]][j], p[ind[b][j]][j]);
            swap(ind[a][j], ind[b][j]);
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 49