Submission #849020

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

potion

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

using namespace std;

typedef pair<int, int> pii;

const int C = 50;

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;
}

void init(int N, int D, int H[]) {
    n = N;
    heights.resize(N);
    for (int i = 0; i < n; i++)
        heights[i] = H[i];
    d = D;
}

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];
}

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

int question(int x, int y, int v) {
    set<int> x_set, y_set;
    for (int i = 0; i < v; i++) {
        int a = changes[i].first, b = changes[i].second;
        if (b == x)
            process(x_set, a);
        else if (a == x)
            process(x_set, b);
        
        if (a == y)
            process(y_set, b);
        else if (b == y)
            process(y_set, a);
    }
    return min_dist(vector<int>(x_set.begin(), x_set.end()), vector<int>(y_set.begin(), y_set.end()));
}

Compilation message (stderr)

potion.cpp: In function 'int min_dist(std::vector<int>, std::vector<int>)':
potion.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < first.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
potion.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i <second.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
potion.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while (pnt1 < first.size() and pnt2 < second.size()) {
      |            ~~~~~^~~~~~~~~~~~~~
potion.cpp:25:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while (pnt1 < first.size() and pnt2 < second.size()) {
      |                                    ~~~~~^~~~~~~~~~~~~~~
potion.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if (pnt1 + 1 == first.size())
      |             ~~~~~~~~~^~~~~~~~~~~~~~~
potion.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         else if (pnt2 + 1 == second.size())
      |                  ~~~~~~~~~^~~~~~~~~~~~~~~~

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