Submission #471380

#	Time	Username	Problem	Language	Result	Execution time	Memory
471380		TheScrasse	ICC (CEOI16_icc)	C++17	0 / 100	299 ms	262148 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 110

mt19937 rng(19938);

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll pr[maxn], f[maxn];
set<ll> cc[maxn];

ll N, A, B;

ll query(ll sza, ll szb, ll a[], ll b[]) {
    // cout << "query" << nl;
    ll i, x = 0, y = 0;
    for (i = 0; i < sza; i++) {
        if (a[i] == A || a[i] == B) x++;
        // cout << a[i] << ' ';
    }
    // cout << nl;
    for (i = 0; i < szb; i++) {
        if (b[i] == A || b[i] == B) y++;
        // cout << b[i] << ' ';
    }
    // cout << nl;

    return (x == 1 && y == 1);
}

/* void setRoad(ll a, ll b) {
    // cout << "set_road " << a _ b << nf;
    if (a < b) swap(a, b);
    if (A < B) swap(A, B);
    if (a == A && b == B) cout << "correct " << a _ b << nf;
    else cout << "wrong" << nf;
} */

ll find(ll x) {
    if (x == pr[x]) return x;
    return pr[x] = find(pr[x]);
}

bool same(ll a, ll b) {
    return (find(a) == find(b));
}

void merge(ll a, ll b) {
    a = find(a); b = find(b);
    if (cc[a].size() < cc[b].size()) {
        swap(a, b); swap(cc[a], cc[b]);
    }
    pr[b] = a;
    for (auto u : cc[b]) cc[a].insert(u);
    cc[b].clear();
}

ll split(ll l, ll r) {
    ll i, tt = 0;
    if (l > r) return l;
    for (i = l; i <= r; i++) {
        if (pr[f[i]] != f[i]) continue;
        if (2 * tt + cc[f[i]].size() >= n) return i;
        tt += cc[f[i]].size();
    }
    return r;
}

void build1(vector<array<ll, 2>> v, vector<ll> &va, vector<ll> &vb, ll bsm) {
    ll i;
    for (i = 0; i <= bsm; i++) {
        k = split(v[i][0], v[i][1]);
        for (j = v[i][0]; j <= v[i][1]; j++) {
            if (pr[f[j]] != f[j]) continue;
            for (auto u : cc[f[j]]) {
                if (j < k) va.pb(u);
                else vb.pb(u);
            }
        }
    }
}

void build2(ll l0, ll l1, ll r0, ll r1, vector<ll> &va, vector<ll> &vb) {
    ll i;
    for (i = l0; i <= l1; i++) {
        if (pr[f[i]] != f[i]) continue;
        for (auto u : cc[f[i]]) va.pb(u);
    }
    for (i = r0; i <= r1; i++) {
        if (pr[f[i]] != f[i]) continue;
        for (auto u : cc[f[i]]) vb.pb(u);
    }
}

void build3(ll x, ll y, ll l, ll r, vector<ll> &va, vector<ll> &vb) {
    for (auto u : cc[f[x]]) {
        va.pb(u); l--;
        if (l == 0) break;
    }
    for (auto u : cc[f[y]]) {
        vb.pb(u); r--;
        if (r == 0) break;
    }
}

void solve4(ll x, ll y, ll l, ll r) {
    // cout << "solve4" << nf;
    ll i, bsl, bsm, bsu, z, w;
    bsl = 0; bsu = l;
    while (bsl != bsu) {
        bsm = (bsl + bsu) / 2;
        vector<ll> va, vb;
        build3(x, y, bsm, r, va, vb);

        ll a[va.size()], b[vb.size()];
        for (i = 0; i < va.size(); i++) a[i] = va[i];
        for (i = 0; i < vb.size(); i++) b[i] = vb[i];

        if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
        else bsl = bsm + 1;
    }
    z = bsl;

    bsl = 0; bsu = r;
    while (bsl != bsu) {
        bsm = (bsl + bsu) / 2;
        vector<ll> va, vb;
        build3(x, y, l, bsm, va, vb);

        ll a[va.size()], b[vb.size()];
        for (i = 0; i < va.size(); i++) a[i] = va[i];
        for (i = 0; i < vb.size(); i++) b[i] = vb[i];

        if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
        else bsl = bsm + 1;
    }
    w = bsl;

    vector<ll> vc, vd;
    build3(x, y, z, w, vc, vd);
    // cout << "set ready " << vc.back() _ vd.back() << nl;
    setRoad(vc.back(), vd.back());
}

void solve3(array<ll, 2> l, array<ll, 2> r) {
    // cout << "solve3 " << l[0] _ l[1] _ r[0] _ r[1] << nf;
    ll i, bsl, bsm, bsu, x, y;
    bsl = l[0]; bsu = l[1];
    while (bsl != bsu) {
        bsm = (bsl + bsu) / 2;
        vector<ll> va, vb;
        build2(l[0], bsm, r[0], r[1], va, vb);

        ll a[va.size()], b[vb.size()];
        for (i = 0; i < va.size(); i++) a[i] = va[i];
        for (i = 0; i < vb.size(); i++) b[i] = vb[i];

        if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
        else bsl = bsm + 1;
    }
    x = bsl;

    bsl = r[0]; bsu = r[1];
    while (bsl != bsu) {
        bsm = (bsl + bsu) / 2;
        vector<ll> va, vb;
        build2(l[0], l[1], r[0], bsm, va, vb);

        ll a[va.size()], b[vb.size()];
        for (i = 0; i < va.size(); i++) a[i] = va[i];
        for (i = 0; i < vb.size(); i++) b[i] = vb[i];

        if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
        else bsl = bsm + 1;
    }
    y = bsl;

    solve4(x, y, cc[f[x]].size(), cc[f[y]].size());
}

void solve2(vector<array<ll, 2>> v) {
    // cout << "solve2" << nf;
    ll i, bsl, bsm, bsu;
    bsl = 0; bsu = (ll)v.size() - 1;
    while (bsl != bsu) {
        bsm = (bsl + bsu) / 2;
        vector<ll> va, vb;
        build1(v, va, vb, bsm);

        ll a[va.size()], b[vb.size()];
        for (i = 0; i < va.size(); i++) a[i] = va[i];
        for (i = 0; i < vb.size(); i++) b[i] = vb[i];

        if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
        else bsl = bsm + 1;
    }

    k = split(v[bsl][0], v[bsl][1]);
    solve3({v[bsl][0], k - 1}, {k, v[bsl][1]});
}

void solve1(vector<array<ll, 2>> v) {
    // cout << "solve1" << nf;
    ll i;
    vector<array<ll, 2>> w;
    for (auto u : v) {
        ll mid = split(u[0], u[1]);
        w.pb({u[0], mid - 1}); w.pb({mid, u[1]});
    }

    vector<ll> va, vb;
    build1(v, va, vb, (ll)v.size() - 1);

    ll a[va.size()], b[vb.size()];
    for (i = 0; i < va.size(); i++) a[i] = va[i];
    for (i = 0; i < vb.size(); i++) b[i] = vb[i];

    if (query(va.size(), vb.size(), a, b) == 0) solve1(w);
    else solve2(v);
}

void run(int N) {
    /* #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> n; */
    n = N;
    for (i = 1; i <= n; i++) {
        pr[i] = i; cc[i].insert(i); f[i] = i;
    }

    for (i = 1; i <= n - 1; i++) {
        // cin >> A >> B;
        // cout << "i = " << i << nf;
        shuffle(f + 1, f + n + 1, rng);
        solve1({{1, n}});
    }
}

/* int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> N;
    run(N);
} */

Compilation message (stderr)

icc.cpp: In function 'long long int split(long long int, long long int)':
icc.cpp:72:38: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   72 |         if (2 * tt + cc[f[i]].size() >= n) return i;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
icc.cpp: In function 'void solve4(long long int, long long int, long long int, long long int)':
icc.cpp:125:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (i = 0; i < va.size(); i++) a[i] = va[i];
      |                     ~~^~~~~~~~~~~
icc.cpp:126:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (i = 0; i < vb.size(); i++) b[i] = vb[i];
      |                     ~~^~~~~~~~~~~
icc.cpp:140:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for (i = 0; i < va.size(); i++) a[i] = va[i];
      |                     ~~^~~~~~~~~~~
icc.cpp:141:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for (i = 0; i < vb.size(); i++) b[i] = vb[i];
      |                     ~~^~~~~~~~~~~
icc.cpp: In function 'void solve3(std::array<long long int, 2>, std::array<long long int, 2>)':
icc.cpp:164:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (i = 0; i < va.size(); i++) a[i] = va[i];
      |                     ~~^~~~~~~~~~~
icc.cpp:165:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for (i = 0; i < vb.size(); i++) b[i] = vb[i];
      |                     ~~^~~~~~~~~~~
icc.cpp:179:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         for (i = 0; i < va.size(); i++) a[i] = va[i];
      |                     ~~^~~~~~~~~~~
icc.cpp:180:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         for (i = 0; i < vb.size(); i++) b[i] = vb[i];
      |                     ~~^~~~~~~~~~~
icc.cpp: In function 'void solve2(std::vector<std::array<long long int, 2> >)':
icc.cpp:200:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |         for (i = 0; i < va.size(); i++) a[i] = va[i];
      |                     ~~^~~~~~~~~~~
icc.cpp:201:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         for (i = 0; i < vb.size(); i++) b[i] = vb[i];
      |                     ~~^~~~~~~~~~~
icc.cpp: In function 'void solve1(std::vector<std::array<long long int, 2> >)':
icc.cpp:224:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for (i = 0; i < va.size(); i++) a[i] = va[i];
      |                 ~~^~~~~~~~~~~
icc.cpp:225:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for (i = 0; i < vb.size(); i++) b[i] = vb[i];
      |                 ~~^~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10