oj.uz

Submission #1039229

# Submission time Handle Problem Language Result Execution time Memory
1039229 2024-07-30T14:54:13 Z Tonyl The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 474 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define submit(a,b) cout << a << " " << b << endl
#define D(x) //cerr << #x << ": " << x << endl;

struct Collection {
    vector<int> nums;

    void flip(int i) {
        /*if (nums.count(i)) nums.erase(i);
        else nums.insert(i);*/
        bool cont = 0;
        trav(a,nums) {if (a == i) {cont = 1;}}

        if (!cont) {
            nums.push_back(i);
            return;
        } 
        vi nums2;
        trav(a,nums) {
            if (a != i) nums2.push_back(a);
        }
        nums = nums2;
    }

    vi get_all() {
        return vi(all(nums));
    }
};

struct TimeTraveller {
    vector<pair<int, Collection*>> history;

    TimeTraveller() {
        history.push_back({-1, new Collection()});
    }

    void flip(int i, int time) {
        Collection *c = new Collection();
        c->nums = (history.back().second)->nums;
        c->flip(i);
        history.push_back({time, c});
    }

    vi get_all(int time) {
        auto p = lower_bound(all(history), pair<int, Collection*>(time+1, nullptr));
        p--;
        return (*p).second->get_all();
    }
};

const int MAX_N = 1e5+2;

int n,d;
vi hs;

TimeTraveller fr[MAX_N];

int get_ans(vi a, vi b) {
    int best = 1e9;

    vi h1, h2;
    trav(aa, a) {
        h1.push_back(hs[aa]);
    }
    sort(all(h1));
    trav(bb, b) {
        h2.push_back(hs[bb]);
    }
    sort(all(h2));

    if (h1.size() == 0) return best;

    int i = 0;
    trav(hb, h2) {
        while (h1[i] < hb && i != h1.size()-1) i++;
        best = min(best, abs(hb - h1[i]));
        if (i!=0) best = min(best, abs(hb - h1[i-1]));
    }

    return best;
}

void init(int N, int D, int H[]) {
    n = N; d = D;
    REP(i,n) hs.push_back(H[i]);
}

void curseChanges(int U, int A[], int B[]) {
    REP(uu, U) {
        int a = A[uu];
        int b = B[uu];
        fr[a].flip(b, uu+1);
        fr[b].flip(a, uu+1);
    }
}

int question(int x, int y, int v) {
    return get_ans(fr[x].get_all(v), fr[y].get_all(v));
}

Compilation message

potion.cpp: In function 'int get_ans(vi, vi)':
potion.cpp:82:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while (h1[i] < hb && i != h1.size()-1) i++;
      |                              ~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9048 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9048 KB Output is correct
2 Correct 8 ms 9048 KB Output is correct
3 Correct 8 ms 9208 KB Output is correct
4 Correct 15 ms 9872 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 46536 KB Output is correct
2 Correct 200 ms 46792 KB Output is correct
3 Correct 138 ms 57488 KB Output is correct
4 Runtime error 198 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 46760 KB Output is correct
2 Runtime error 205 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10840 KB Output is correct
2 Correct 52 ms 11352 KB Output is correct
3 Correct 74 ms 11608 KB Output is correct
4 Correct 468 ms 19284 KB Output is correct
5 Correct 474 ms 17496 KB Output is correct
6 Correct 69 ms 11864 KB Output is correct
7 Correct 367 ms 17236 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9048 KB Output is correct
2 Correct 8 ms 9048 KB Output is correct
3 Correct 8 ms 9048 KB Output is correct
4 Correct 8 ms 9208 KB Output is correct
5 Correct 15 ms 9872 KB Output is correct
6 Correct 211 ms 46536 KB Output is correct
7 Correct 200 ms 46792 KB Output is correct
8 Correct 138 ms 57488 KB Output is correct
9 Runtime error 198 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -