oj.uz

Submission #366534

# Submission time Handle Problem Language Result Execution time Memory
366534 2021-02-14T10:49:18 Z ne4eHbKa Tenis (COCI20_tenis) C++17
55 / 110
 141 ms 14316 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 1e5 + 5;

struct fenwick {
    int f[N] {};
    void add(int i) {for(i = N - 2 - i; i < N; i += i & -i) ++f[i];}
    int get(int i) {int v{}; for(i = N - 2 - i; i; i -= i & -i) v += f[i]; return v;}
};

fenwick f0, f01, f02, f012,
        f1, f10, f12, f102,
        f2, f20, f21, f201;
int p0[N], p1[N], p2[N], r0[N], r1[N], r2[N], n, p[N];
int c0, c1, c2, s[N];

void add(int &a, int &b, const int c) {
    a += c;
    b += c;
}

int min(const int a, const int b, const int c) {
    return min(a, min(b, c));
}

set<pii> f;

void check(int i, int j) {
    if(p[i] != p[j]) return;
    f.insert({i, j});
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> r0[i], p0[--r0[i]] = i;
    for(int i = 0; i < n; ++i)
        cin >> r1[i], p1[--r1[i]] = i;
    for(int i = 0; i < n; ++i)
        cin >> r2[i], p2[--r2[i]] = i;
    for(int i = 0; i < n; ++i)
        p[i] = min(p0[i], p1[i], p2[i]);
    for(int i = n - 1; ~i; --i) {
        int v;
        bool b0, b1;

        v = r0[i];
        if(p1[v] >  i && p2[v] >  i) add(c0, s[v], f0  .get(i + 1)), check(v, r1[i]), check(v, r2[i]);
        if(p1[v] == i && p2[v] >  i) add(c0, s[v], f01 .get(i + 1)),                  check(v, r2[i]);
        if(p1[v] >  i && p2[v] == i) add(c0, s[v], f02 .get(i + 1)), check(v, r1[i])                 ;
        if(p1[v] == i && p2[v] == i) add(c0, s[v], f012.get(i + 1))                                  ;

        v = r1[i];
        if(p0[v] >  i && p2[v] >  i) add(c1, s[v], f1  .get(i + 1)), check(v, r0[i]), check(v, r2[i]);
        if(p0[v] == i && p2[v] >  i) add(c1, s[v], f10 .get(i + 1)),                  check(v, r2[i]);
        if(p0[v] >  i && p2[v] == i) add(c1, s[v], f12 .get(i + 1)), check(v, r0[i])                 ;
        if(p0[v] == i && p2[v] == i) add(c1, s[v], f102.get(i + 1))                                  ;

        v = r2[i];
        if(p0[v] >  i && p1[v] >  i) add(c2, s[v], f2  .get(i + 1)), check(v, r0[i]), check(v, r1[i]);
        if(p0[v] == i && p1[v] >  i) add(c2, s[v], f20 .get(i + 1)),                  check(v, r1[i]);
        if(p0[v] >  i && p1[v] == i) add(c2, s[v], f21 .get(i + 1)), check(v, r0[i])                 ;
        if(p0[v] == i && p1[v] == i) add(c2, s[v], f201.get(i + 1))                                  ;

        v = r0[i];
        b0 = p1[v] >= i;
        b1 = p2[v] >= i;
                     f0.add(p[v]);
        if(b0)       f01.add(p[v]);
        if(b1)       f02.add(p[v]);
        if(b0 && b1) f012.add(p[v]);

        v = r1[i];
        b0 = p0[v] >  i;
        b1 = p2[v] >= i;
                     f1.add(p[v]);
        if(b0)       f10.add(p[v]);
        if(b1)       f12.add(p[v]);
        if(b0 && b1) f102.add(p[v]);

        v = r2[i];
        b0 = p0[v] >  i;
        b1 = p1[v] >  i;
                     f2.add(p[v]);
        if(b0)       f20.add(p[v]);
        if(b1)       f21.add(p[v]);
        if(b0 && b1) f201.add(p[v]);
    }
    for(const pii &P : f) {
        int i, j;
        tie(i, j) = P;
        typedef tuple<int, int, int> ti;
        ti z {n, n, 0};
        p0[i] < p0[j]
            ? umin(z, ti{p0[i], p0[j], 1})
            : umin(z, ti{p0[j], p0[i], 0});
        p1[i] < p1[j]
            ? umin(z, ti{p1[i], p1[j], 3})
            : umin(z, ti{p1[j], p1[i], 2});
        p2[i] < p2[j]
            ? umin(z, ti{p2[i], p2[j], 5})
            : umin(z, ti{p2[j], p2[i], 4});
        int fi, se, th;
        tie(fi, se, th) = z;
        if((th & 1) && fi < n)
            add(th > 1 ? th > 3 ? c2 : c1 : c0, s[i], 1);
    }
    cout << -1 _ c1 _ c2 << '\n';
    for(int i = 0; i < n; ++i) cout << s[i] << ' ';
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Subtask #1
17.5 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Partially correct
2 Partially correct 1 ms 364 KB Partially correct
3 Partially correct 1 ms 492 KB Partially correct

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Partially correct
2 Partially correct 1 ms 364 KB Partially correct
3 Partially correct 1 ms 492 KB Partially correct
4 Partially correct 3 ms 876 KB Partially correct

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Partially correct
2 Partially correct 1 ms 364 KB Partially correct
3 Partially correct 1 ms 492 KB Partially correct
4 Partially correct 3 ms 876 KB Partially correct
5 Partially correct 43 ms 5996 KB Partially correct
6 Partially correct 69 ms 8684 KB Partially correct
7 Partially correct 109 ms 11628 KB Partially correct
8 Partially correct 141 ms 14316 KB Partially correct
9 Partially correct 132 ms 11372 KB Partially correct
10 Partially correct 71 ms 9708 KB Partially correct