Submission #895615


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define sqr(x) ((x) * (x))
#define pb push_back
#define mp make_pair
#define ins insert
#define er erase
#define bg begin()
#define ed end()
#define X first
#define Y second
#define fin(name) freopen(name, "r", stdin)
#define fout(name) freopen(name, "w", stdout)
#define files(name) fin(name".in"); fout(name".out")
#define enter cout << "\n"
#define space cout << " "
#define endl "\n"
#define fi(st,n) for (int i = (st); i <= (n); ++i)
#define fj(st,n) for (int j = (st); j <= (n); ++j)
#define fk(st,n) for (int k = (st); k <= (n); ++k)
#define fq(st,n) for (int q = (st); q <= (n); ++q)
#define fw(st,n) for (int w = (st); w <= (n); ++w)
#define ff(i, st, n) for (int (i) = (st); (i) <= (n); ++(i))
#define ei(st,n) for (int i = (st); i >= (n); --i)
#define ej(st,n) for (int j = (st); j >= (n); --j)
#define ek(st,n) for (int k = (st); k >= (n); --k)
#define ef(i, st, n) for (int (i) = (st); (i) >= (n); --(i))
#define ri(st,n) for (int i = (st); i < (n); ++i)
#define rj(st,n) for (int j = (st); j < (n); ++j)
#define rk(st,n) for (int k = (st); k < (n); ++k)
#define rq(st,n) for (int q = (st); q < (n); ++q)
#define rf(i, st, n) for (int (i) = (st); (i) < (n); ++(i))
#define clean(a) memset((a),0,sizeof (a))
#define sync ios_base::sync_with_stdio(0);cin.tie(0)
#define y1 dsklmlvmd

typedef long long ll;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int inf = (int)1e9;
const dbl eps = (dbl) 1e-8;
const int mod = (int) 1000000007;
const int maxn = (int) 1e5 + 5;
//const dbl M_PI = (dbl)2 * (dbl)acos(0);

//cout<<fixed<<setprecision(10);
//srand(time(0));

int n, m, T, a[maxn], khm, x, y, t[maxn], en[maxn], zp;
vector <int> vh, vc[maxn];

int main()
{
//    fin("t.in");
    sync;
    cin >> n >> m;
    cin >> T;
    fi(1, T) {
        cin >> a[i];
        vc[a[i]].pb(i);
    }
    fi(1, n) {
        en[i] = T;
    }
    vh.clear();
    khm = -1;
    ei(T, 1) {
        if (t[a[i]])
            continue;
        vh.pb(a[i]);
        t[a[i]] = i;
        x = n;
        ej((int)vc[a[i]].size() - 1, 0) {
            if (en[x] < vc[a[i]][j]) {
                continue;
            }
            en[x] = vc[a[i]][j] - 1;
            --x;
            if (x == 0)
                break;
        }
        if (khm == -1) {
            ej(x, 1) {
                en[j] = 0;
                khm = (int)vh.size() - 1;
                zp = i;
            }  
        }
    }
    if (khm != -1) {
        y = 0;
//        cout << khm << endl;
        ri(khm, vh.size()) {
            ++y;
            while (t[y] > zp) {
                ++y;
            }
            if (vh[i] != y) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Submission Info

Submission Time
Task E - LRU Puzzle
User mHuman
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 2989 Byte
Status AC
Exec Time 24 ms
Memory 7420 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 4
AC × 76
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt
Case Name Status Exec Time Memory
0_00.txt AC 4 ms 2560 KB
0_01.txt AC 5 ms 2560 KB
0_02.txt AC 5 ms 2560 KB
0_03.txt AC 5 ms 2560 KB
1_00.txt AC 5 ms 2560 KB
1_01.txt AC 4 ms 2560 KB
1_02.txt AC 12 ms 3960 KB
1_03.txt AC 12 ms 3960 KB
1_04.txt AC 11 ms 3960 KB
1_05.txt AC 11 ms 3960 KB
1_06.txt AC 22 ms 7420 KB
1_07.txt AC 23 ms 7420 KB
1_08.txt AC 22 ms 7420 KB
1_09.txt AC 23 ms 7420 KB
1_10.txt AC 20 ms 5120 KB
1_11.txt AC 20 ms 5120 KB
1_12.txt AC 20 ms 5120 KB
1_13.txt AC 20 ms 5120 KB
1_14.txt AC 19 ms 5120 KB
1_15.txt AC 19 ms 5120 KB
1_16.txt AC 19 ms 5120 KB
1_17.txt AC 19 ms 5120 KB
1_18.txt AC 22 ms 6656 KB
1_19.txt AC 22 ms 5248 KB
1_20.txt AC 23 ms 6524 KB
1_21.txt AC 24 ms 7036 KB
1_22.txt AC 22 ms 6652 KB
1_23.txt AC 23 ms 5248 KB
1_24.txt AC 22 ms 6780 KB
1_25.txt AC 24 ms 5500 KB
1_26.txt AC 13 ms 3712 KB
1_27.txt AC 12 ms 3712 KB
1_28.txt AC 16 ms 3840 KB
1_29.txt AC 15 ms 3840 KB
1_30.txt AC 15 ms 3968 KB
1_31.txt AC 15 ms 3968 KB
1_32.txt AC 14 ms 3840 KB
1_33.txt AC 16 ms 4096 KB
1_34.txt AC 21 ms 4608 KB
1_35.txt AC 21 ms 4992 KB
1_36.txt AC 21 ms 4352 KB
1_37.txt AC 22 ms 4864 KB
1_38.txt AC 22 ms 5760 KB
1_39.txt AC 22 ms 6396 KB
1_40.txt AC 21 ms 5760 KB
1_41.txt AC 23 ms 6528 KB
1_42.txt AC 13 ms 3712 KB
1_43.txt AC 13 ms 3712 KB
1_44.txt AC 13 ms 3712 KB
1_45.txt AC 13 ms 3840 KB
1_46.txt AC 15 ms 3840 KB
1_47.txt AC 14 ms 3968 KB
1_48.txt AC 16 ms 3968 KB
1_49.txt AC 16 ms 4096 KB
1_50.txt AC 15 ms 3840 KB
1_51.txt AC 13 ms 3712 KB
1_52.txt AC 16 ms 3968 KB
1_53.txt AC 15 ms 3840 KB
1_54.txt AC 15 ms 3840 KB
1_55.txt AC 13 ms 3712 KB
1_56.txt AC 19 ms 4352 KB
1_57.txt AC 18 ms 4224 KB
1_58.txt AC 11 ms 3584 KB
1_59.txt AC 12 ms 3584 KB
1_60.txt AC 12 ms 3584 KB
1_61.txt AC 12 ms 3584 KB
1_62.txt AC 13 ms 3840 KB
1_63.txt AC 12 ms 3708 KB
1_64.txt AC 12 ms 3584 KB
1_65.txt AC 14 ms 3840 KB
1_66.txt AC 12 ms 4096 KB
1_67.txt AC 11 ms 4096 KB
1_68.txt AC 12 ms 4096 KB
1_69.txt AC 12 ms 4096 KB
1_70.txt AC 11 ms 4096 KB
1_71.txt AC 14 ms 4224 KB