oj.uz

Submission #228968

# Submission time Handle Problem Language Result Execution time Memory
228968 2020-05-03T08:00:03 Z Vimmer Kocka (COCI18_kocka) C++14
70 / 70
 49 ms 6016 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 432 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4992 KB Output is correct
2 Correct 45 ms 6016 KB Output is correct
3 Correct 46 ms 6016 KB Output is correct
4 Correct 33 ms 6016 KB Output is correct
5 Correct 45 ms 6016 KB Output is correct
6 Correct 47 ms 6016 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4992 KB Output is correct
2 Correct 34 ms 6016 KB Output is correct
3 Correct 47 ms 6016 KB Output is correct
4 Correct 38 ms 6008 KB Output is correct
5 Correct 47 ms 6016 KB Output is correct
6 Correct 41 ms 6016 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5112 KB Output is correct
2 Correct 35 ms 6016 KB Output is correct
3 Correct 46 ms 6016 KB Output is correct
4 Correct 48 ms 6016 KB Output is correct
5 Correct 48 ms 6016 KB Output is correct
6 Correct 35 ms 6016 KB Output is correct