Submission #641712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641712	2022-09-17T13:26:26 Z	Itamar	The Potion of Great Power (CEOI20_potion)	C++14	14 / 100	657 ms	40224 KB

potion

using namespace std;
#include <iostream>
#include <vector>
#define pi pair<int,int>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
const int siz = 1e5;
set<int> f[siz];
//pi padre[siz];
//int ans[siz];
int h[siz];
vector<pi> fi[siz];
vi fn[siz];
//bool ch[siz];
const ll m = 1e9 + 7;
bool t;
int n;

void init(int N, int D, int F[]) {
    n = N;
    for (int i = 0; i < n; i++) {
        h[i] = F[i];
    }
}
void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        if (f[A[i]].find(B[i]) == f[A[i]].end()) {
            f[A[i]].insert(B[i]);
            f[B[i]].insert(A[i]);
        }
        else {
            f[A[i]].erase(B[i]);
            f[B[i]].erase(A[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int t : f[i]) {
            fi[i].push_back({ h[t],t });
        }
        sort(fi[i].begin(), fi[i].end());
        for (pi p : fi[i]) {
            fn[i].push_back(p.first);
        }
    }
}
int question(int X, int Y, int V) {
    vi v1 = fn[X],  v2 = fn[Y];
    int siz1 = v1.size(), siz2 = v2.size();
    int ans = 1e9;
    for (int i = 0; i < siz1; i++) {
        int in = upper_bound(v2.begin(), v2.end(), v1[i]) - v2.begin();
        
        if (in > 0) {
           ans = min(ans, abs(v1[i] - v2[in - 1]));
        }
        if (in < siz2) {
            ans = min(ans, abs(v1[i] - v2[in ]));
        }
    }
    return ans;
}
/*
int main() {
    int N, D, U, Q;
    std::ios::sync_with_stdio(false); std::cin.tie(NULL);
    std::cin >> N >> D >> U >> Q;

    int* F = new int[N];
    for (int i = 0; i < N; i++)
        std::cin >> F[i];
    init(N, D, F);

    int* A = new int[U], * B = new int[U];
    for (int i = 0; i < U; i++) {
        std::cin >> A[i] >> B[i];
    }
    curseChanges(U, A, B);

    bool correct = true;
    for (int i = 0; i < Q; i++) {
        int X, Y, V, CorrectAnswer;
        std::cin >> X >> Y >> V >> CorrectAnswer;
        int YourAnswer = question(X, Y, V);
        if (YourAnswer != CorrectAnswer) {
            std::cout << "WA! Question: " << i
                << " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
                << "Your answer: " << YourAnswer
                << " Correct Answer: " << CorrectAnswer << std::endl;
            correct = false;
        }
        else {
            std::cerr << YourAnswer << " - OK" << std::endl;
        }
    }

    if (correct) {
        std::cout << "Correct." << std::endl;
    }
    else std::cout << "Incorrect." << std::endl;
    return 0;
}
*/
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Subtask #1
0 / 0.0

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

Subtask #2
0 / 17.0

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

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	312 ms	40224 KB	Output is correct
2	Correct	319 ms	40124 KB	Output is correct
3	Correct	111 ms	12092 KB	Output is correct
4	Correct	448 ms	23644 KB	Output is correct
5	Correct	328 ms	37280 KB	Output is correct
6	Correct	657 ms	21468 KB	Output is correct
7	Correct	203 ms	21600 KB	Output is correct