Submission #849220

#	Time	Username	Problem	Language	Result	Execution time	Memory
849220		faruk	The Potion of Great Power (CEOI20_potion)	C++17	17 / 100	3066 ms	44140 KiB

potion

#include <bits/stdc++.h>    	
#define all(a) a.begin(), a.end()

using namespace std;

typedef pair<int, int> pii;

const int C = 20;

struct checkpoint {
    int time;
    vector<int> guys;

    checkpoint() {}
    checkpoint(int T, vector<int> sett) {
        time = T;
        guys = sett;
    }
    bool operator<(const checkpoint &a) const {return time < a.time;}
};

int n, d, u;
vector<int> heights;
vector<pii> changes;

int min_dist(vector<int> first, vector<int> second) {
    if (first.empty() || second.empty())
        return 1e9;
    for (int i = 0; i < first.size(); i++)
        first[i] = heights[first[i]];
    for (int i = 0; i <second.size(); i++)
        second[i] = heights[second[i]];
    sort(all(first));
    sort(all(second));

    int pnt1 = 0, pnt2 = 0, out = 2e9;
    while (pnt1 < first.size() and pnt2 < second.size()) {
        out = min(out, abs(first[pnt1] - second[pnt2]));

        if (pnt1 + 1 == first.size())
            pnt2++;
        else if (pnt2 + 1 == second.size())
            pnt1++;
        else if (first[pnt1] < second[pnt2])
            pnt1++;
        else
            pnt2++;
    }
    return out;
}

vector<vector<checkpoint> > states;
vector<vector<pii> > individ_updates;
void init(int N, int D, int H[]) {
    n = N;
    individ_updates.resize(n);
    states.resize(n);
    heights.resize(N);
    for (int i = 0; i < n; i++)
    {
        heights[i] = H[i];
        states[i].push_back(checkpoint(-1, vector<int>()));
    }
    d = D;
    states.resize(n);
}

void process(set<int> &set, int &val) {
    if (set.count(val))
        set.erase(val);
    else
        set.insert(val);
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    changes.resize(u);
    for (int i = 0; i < u; i++)
    {
        changes[i].first = A[i], changes[i].second = B[i];
        individ_updates[A[i]].push_back({i, B[i]});
        individ_updates[B[i]].push_back({i, A[i]});
    }
    
    vector<int> time_since_last(n, 0);
    vector<set<int> > guys(n);
    for (int i = 0; i < u; i++) {
        int a = changes[i].first, b = changes[i].second;
        process(guys[a], b);
        process(guys[b], a);
        if (time_since_last[a] == C) {
            states[a].push_back(checkpoint(i, vector<int>(all(guys[a]))));
            time_since_last[a] = 0;
        }
        if (time_since_last[b] == C) {
            states[b].push_back(checkpoint(i, vector<int>(all(guys[b]))));
            time_since_last[b] = 0;
        }
        time_since_last[a]++;
        time_since_last[b]++;
    }
}

// todo; finish get set
vector<int> get_set(int x, int v) {
    checkpoint check = *prev(upper_bound(all(states[x]), checkpoint(v, vector<int>())));
    set<int> guys(all(check.guys));
    int idx = lower_bound(all(individ_updates[x]), pii(check.time, 1e9)) - individ_updates[x].begin();
    for (; idx < individ_updates[x].size() and individ_updates[x][idx].first < v; idx++)
        process(guys, individ_updates[x][idx].second);
    return vector<int>(all(guys));
}

int question(int x, int y, int v) {
    vector<int> x_set = get_set(x, v), y_set = get_set(y, v);
    return min_dist(x_set, y_set);
}

Compilation message (stderr)

potion.cpp: In function 'int min_dist(std::vector<int>, std::vector<int>)':
potion.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < first.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
potion.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i <second.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
potion.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (pnt1 < first.size() and pnt2 < second.size()) {
      |            ~~~~~^~~~~~~~~~~~~~
potion.cpp:37:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (pnt1 < first.size() and pnt2 < second.size()) {
      |                                    ~~~~~^~~~~~~~~~~~~~~
potion.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (pnt1 + 1 == first.size())
      |             ~~~~~~~~~^~~~~~~~~~~~~~~
potion.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         else if (pnt2 + 1 == second.size())
      |                  ~~~~~~~~~^~~~~~~~~~~~~~~~
potion.cpp: In function 'std::vector<int> get_set(int, int)':
potion.cpp:109:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (; idx < individ_updates[x].size() and individ_updates[x][idx].first < v; idx++)
      |            ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30