oj.uz

Submission #366785

# Submission time Handle Problem Language Result Execution time Memory
366785 2021-02-15T09:48:49 Z kartel Tenis (COCI20_tenis) C++14
110 / 110
 156 ms 8164 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 1e5 + 500;

set <pii> se;
int where[N][4];
int a[4][N];
int mn[N];
vector <int> bestest[9];
ll cnt[4], ans[N], n;

void check(int a, int b, int p) {
    if (a == b || mn[a] != p || mn[b] != p)
        return;

    pii P = {min(a, b), max(a, b)};

    if (se.count(P))
        return;

    se.insert(P);

    pii p0 = {min(where[a][0], where[b][0]), max(where[a][0], where[b][0])};
    pii p1 = {min(where[a][1], where[b][1]), max(where[a][1], where[b][1])};
    pii p2 = {min(where[a][2], where[b][2]), max(where[a][2], where[b][2])};

    if (p2 < p1 && p2 < p0) {
        cnt[2]++;
        ans[a] += (where[a][2] > where[b][2]);
        ans[b] += (where[b][2] > where[a][2]);
    }
    else if (p1 < p0) {
        cnt[1]++;
        ans[a] += (where[a][1] > where[b][1]);
        ans[b] += (where[b][1] > where[a][1]);
    }
    else {
        cnt[0]++;
        ans[a] += (where[a][0] > where[b][0]);
        ans[b] += (where[b][0] > where[a][0]);
    }
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("volley.in");
//	out("volley.out");
//    in("input.txt");
//    out("output.txt");

//    clock_t tStart = clock();
    cin >> n;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            int x;

            cin >> x;
            x--;

            a[i][j] = x;
            where[x][i] = j;
        }
    }

    for (int i = 0; i < n; i++) {
        mn[i] = min({where[i][0],
                     where[i][1],
                     where[i][2]});

        int mask = 0;

        for (int j = 0; j < 3; j++) {
            if (where[i][j] == mn[i]) {
                mask |= (1 << j);
            }
        }

//      	cerr << i << " " << mask << el;

        bestest[mask].pb(mn[i]);
    }

    for (int i = 0; i < 8; i++) {
        sort(all(bestest[i]));
    }

    for (int i = 0; i < n; i++) {
        for (int mask = 1; mask < 8; mask++) {
            int ps = lower_bound(all(bestest[mask]), mn[i]) - bestest[mask].begin();

            int p = -1;

            for (int k = 0; k < 3; k++) {
                if (!(mask & (1 << k)))
                    continue;

                if (p == -1 || where[i][k] < where[i][p])
                    p = k;
            }

//            cout << i << " " << mask <<  " " << ps << " " << p << el;

            assert(p != -1);

            cnt[p] += ps;
            ans[i] += ps;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++)
        for (int k = j + 1; k < 3; k++) {
            check(a[j][i], a[k][i], i);
        }
    }

    for (int i = 0; i < 3; i++) {
        cout << cnt[i] << " ";
    }

    cout << el;

    for (int i = 0; i < n; i++)
        cout << n - 1 - ans[i] << " ";
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 3 ms 620 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 46 ms 3436 KB Output is correct
6 Correct 72 ms 5228 KB Output is correct
7 Correct 98 ms 6636 KB Output is correct
8 Correct 136 ms 8164 KB Output is correct
9 Correct 156 ms 7784 KB Output is correct
10 Correct 118 ms 5788 KB Output is correct