Submission #540122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
540122	2022-03-19T09:44:34 Z	yuto1115	The Potion of Great Power (CEOI20_potion)	C++17	14 / 100	1146 ms	56388 KB

potion

// #include "grader.cpp"
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template <class T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> void vecout(const vector<T> &v, char div = '\n') {
    int n = SZ(v);
    rep(i, n) cout << v[i] << (i == n - 1 ? '\n' : div);
}

namespace {
int n, d, u;
vi h, a, b;
vi conv;
int bc;
vector<vector<set<int>>> gs;
} // namespace

void init(int N, int D, int H[]) {
    n = N;
    d = D;
    h = vi(H, H + N);
    vi ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) { return h[i] < h[j]; });
    conv.resize(n);
    rep(i, n) conv[ord[i]] = i;
    sort(all(h));
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    a = vi(A, A + U);
    b = vi(B, B + U);
    for (int &i : a) i = conv[i];
    for (int &i : b) i = conv[i];
    // bc = int(sqrt((double)n * u / 50000));
    bc = u;
    chmax(bc, 1);
    gs.reserve(u / bc + 1);
    vector<set<int>> G(n);
    gs.pb(G);
    rep(i, u) {
        if (G[a[i]].count(b[i])) {
            G[a[i]].erase(b[i]);
            G[b[i]].erase(a[i]);
        } else {
            G[a[i]].insert(b[i]);
            G[b[i]].insert(a[i]);
        }
        if ((i + 1) % bc == 0) gs.pb(G);
    }
}

int question(int x, int y, int v) {
    x = conv[x], y = conv[y];
    int now = v / bc * bc;
    const set<int> &sa = gs[v / bc][x], &sb = gs[v / bc][y];
    // rep2(i, now, v) {
    //     if (a[i] == x or b[i] == x) {
    //         if (b[i] == x) swap(a[i], b[i]);
    //         if (sa.count(b[i]))
    //             sa.erase(b[i]);
    //         else
    //             sa.insert(b[i]);
    //     }
    //     if (a[i] == y or b[i] == y) {
    //         if (b[i] == y) swap(a[i], b[i]);
    //         if (sb.count(b[i]))
    //             sb.erase(b[i]);
    //         else
    //             sb.insert(b[i]);
    //     }
    // }
    assert(SZ(sa) <= d);
    assert(SZ(sb) <= d);
    int ans = 1000000000;
    if (sa.empty() or sb.empty()) return ans;
    auto it = sb.begin();
    for (int i : sa) {
        while (it != sb.end() and *it < i) ++it;
        if (it != sb.begin()) chmin(ans, h[i] - h[*prev(it)]);
        if (it == sb.end()) break;
        chmin(ans, h[*it] - h[i]);
    }
    return ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:90:9: warning: unused variable 'now' [-Wunused-variable]
   90 |     int now = v / bc * bc;
      |         ^~~

Subtask #1
0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	208 KB	Incorrect
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	592 KB	Incorrect
2	Halted	0 ms	0 KB	-

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	346 ms	56388 KB	Output is correct
2	Correct	365 ms	56240 KB	Output is correct
3	Correct	155 ms	18800 KB	Output is correct
4	Correct	742 ms	22280 KB	Output is correct
5	Correct	421 ms	42160 KB	Output is correct
6	Correct	1146 ms	29376 KB	Output is correct
7	Correct	310 ms	29308 KB	Output is correct