oj.uz

Submission #849020

# Submission time Handle Problem Language Result Execution time Memory
849020 2023-09-13T22:10:56 Z faruk The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 4968 KB 
#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

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 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 9 ms 1528 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 4968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3033 ms 4964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 856 KB Output is correct
2 Correct 545 ms 604 KB Output is correct
3 Correct 2740 ms 856 KB Output is correct
4 Execution timed out 3099 ms 744 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 9 ms 1528 KB Output is correct
6 Execution timed out 3043 ms 4968 KB Time limit exceeded
7 Halted 0 ms 0 KB -