제출 #1343172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1343172		Math4Life2020	Just Long Neckties 2 (JOI25_ho_t4)	C++20	72 / 100	3091 ms	46220 KiB

Main

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

using ll = int; using pii = pair<ll,ll>;

const ll Mm = 22;

inline ll l2(ll x) {
    return (31-__builtin_clz(x));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    vector<ll> A(N);
    for (ll i=0;i<N;i++) {
        cin >> A[i]; A[i]--;
    }
    vector<ll> ploc[Mm][Mm]; //location of pairs
    for (ll a=0;a<Mm;a++) {
        for (ll b=0;b<Mm;b++) {
            ploc[a][b].push_back(N-1);
        }
    }
    for (ll i=(N-2);i>=0;i--) {
        ploc[min(A[i],A[i+1])][max(A[i],A[i+1])].push_back(i);
    }
    ll mskf[Mm+1]; //this many ones
    for (ll x=0;x<=Mm;x++) {
        mskf[x]=(1<<x)-1;
    }
    for (ll T=1;T<=Mm;T++) {
        vector<ll> qry[N];
        qry[0].push_back((1<<T)-1);
        vector<ll> ploc0[Mm][Mm];
        for (ll a=0;a<Mm;a++) {
            for (ll b=0;b<Mm;b++) {
                ploc0[a][b]=ploc[a][b];
            }
        }
        for (ll x=0;x<N;x++) {
            ll a = 0; ll b = 0;
            if (x>0) {
                a = min(A[x-1],A[x]);
                b = max(A[x-1],A[x]);
            }
            if (!qry[x].empty()) {
                sort(qry[x].begin(),qry[x].end());
                qry[x].erase(unique(qry[x].begin(),qry[x].end()),qry[x].end());
                vector<ll> mskv1;
                for (ll msk: qry[x]) {
                    if ((msk&mskf[a+1])!=0) {
                        ll la = l2(msk&mskf[a+1]);
                        mskv1.push_back(msk^(1<<a)^(1<<la));
                    }
                    if ((msk&mskf[b+1])!=0) {
                        ll lb = l2(msk&mskf[b+1]);
                        mskv1.push_back(msk^(1<<b)^(1<<lb));
                    }
                }
                for (ll msk: mskv1) {
                    ll xf = N-1;
                    for (ll p0=0;p0<(Mm-1);p0++) {
                        if (1^((msk>>p0)&1)) {
                            for (ll p1=(p0);p1<Mm;p1++) {
                                if (1^((msk>>p1)&1)) {
                                    xf = min(xf,ploc0[p0][p1].back());
                                }
                            }
                        }
                    }
                    xf++;
                    if (xf==N) {
                        cout << T << "\n"; exit(0);
                    }
                    qry[xf].push_back(msk);
                }
            }
            if (x>=1) {
                ploc0[a][b].pop_back();
            }
        }
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 10 / 10
• Subtask 3: 6 / 6
• Subtask 4: 12 / 12
• Subtask 5: 18 / 18
• Subtask 6: 26 / 26
• Subtask 7: 0 / 10
• Subtask 8: 0 / 18