Submission #228968

#	Time	Username	Problem	Language	Result	Execution time	Memory
228968		Vimmer	Kocka (COCI18_kocka)	C++14	70 / 70	49 ms	6016 KiB

kocka

#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) ll(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)

using namespace std;

//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;

typedef short int si;

//typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;


ll mx[N], mn[N], n;

void ed()
{
    cout << "NE" << endl;

    exit(0);
}

int main()
{
   // freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    ll a[n][4];

    for (ll i = 0; i < n; i++) {cin >> a[i][0]; if (a[i][0] == -1) a[i][0] = n; mn[i] = mx[i] = 1e9;}

    for (ll i = 0; i < n; i++) {cin >> a[i][1]; if (a[i][1] == -1) a[i][1] = n;}

    for (ll i = 0; i < n; i++) {cin >> a[i][2]; if (a[i][2] == -1) a[i][2] = n;}

    for (ll i = 0; i < n; i++) {cin >> a[i][3]; if (a[i][3] == -1) a[i][3] = n;}

    for (ll i = 0; i < n; i++)
    {
        if ((a[i][0] == n || a[i][1] == n) && a[i][0] != a[i][1]) ed();

        if ((a[i][2] == n || a[i][3] == n) && a[i][2] != a[i][3]) ed();

        if (a[i][2] != n)
        {
            int x = a[i][2];

            mn[x] = min(mn[x], i);

            mx[x] = min(mx[x], n - i - 1);

            if (a[i][2] + a[i][3] + 1 != n)
            {
                ll x = n - a[i][3] - 1;

                mn[x] = min(mn[x], i);

                mx[x] = min(mx[x], ll(n) - i - 1);
            }
        }

        if (a[i][0] != n && a[i][0] + a[i][1] >= n) ed();

        if (a[i][2] != n && a[i][2] + a[i][3] >= n) ed();
    }

    for (int i = 0; i < n; i++)
    {
        if (a[i][0] > mn[i]) ed();

        if (a[i][1] > mx[i]) ed();

        if (a[i][0] == n) continue;

        int p = a[i][0];

        if (a[p][2] > i) ed();

        if (n - a[p][3] - 1 < i) ed();

        p = n - a[i][1] - 1;

        if (a[p][2] > i) ed();

        if (n - a[p][3] - 1 < i) ed();
    }

    cout << "DA" << endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14