Submission #885553

#	Time	Username	Problem	Language	Result	Execution time	Memory
885553		SkillIssueWAGuy	The Potion of Great Power (CEOI20_potion)	C++14	38 / 100	347 ms	262144 KiB

potion

#include<vector>
#include<utility>
#include<cmath>
#include<algorithm>
using namespace std;
namespace cj{
    vector<int> h, a, b;
    int n, d, u, sqrtu;
    vector<vector<vector<int>>> big;
    vector<vector<pair<int,int>>> graph;
    vector<vector<vector<pair<int,int>>>> small;
    vector<int> bs;
    bool Comp(pair<int,int> A, pair<int,int> B){
        if (h[A.first] == h[B.first]){
            return A.first < B.first;
        }
        return h[A.first] < h[B.first];
    }
    inline void push(vector<int> &V, int val){
        if (V.empty()){
            V.push_back(val);
        }
        else if (V.back() != val){
            V.push_back(val);
        }
        else {
            V.pop_back();
        }
    }
}

void init(int N, int D, int H[]) {
    cj::n = N;
    cj::d = D;
    cj::h = vector<int>(N);
    cj::graph = vector<vector<pair<int,int>>>(cj::n, vector<pair<int,int>>(0));
    for (int i = 0; i < N; i++){
        cj::h[i] = H[i];
    }
}

void curseChanges(int U, int A[], int B[]) {
    cj::u = U;
    cj::a = cj::b = vector<int>(U);
    for (int i = 0; i < U; i++){
        cj::a[i] = A[i];
        cj::b[i] = B[i];
    }
    cj::sqrtu = floor(sqrt(cj::u));
    for (int i = 0; i < U; i++){
        cj::graph[cj::a[i]].push_back({cj::b[i], i});
        cj::graph[cj::b[i]].push_back({cj::a[i], i});
    }
    int p = 0;
    while (p < U){
        cj::bs.push_back(p);
        p += cj::sqrtu;
    }
    cj::bs.push_back(cj::u);
    for (int i = 0; i < cj::n; i++){
        sort(cj::graph[i].begin(), cj::graph[i].end(), cj::Comp);
    }
    for (int i = 0; i < cj::bs.size() -1; i++){
        cj::big.push_back(vector<vector<int>>(cj::n, vector<int>(0)));
        cj::small.push_back(vector<vector<pair<int,int>>>(cj::n, vector<pair<int,int>>(0)));
        for (int j = 0; j < cj::n; j++){
            for (pair<int,int> k : cj::graph[j]){
                if (cj::bs[i] <= k.second && cj::bs[i+1] > k.second){
                    cj::small[i][j].push_back(k);
                }
                if (cj::bs[i] > k.second){
                    cj::push(cj::big[i][j], k.first);
                }
            }
        }
    }
}

int question(int x, int y, int v) {
    v--;
    if (v == -1) return 1e9;
    int slot;
    for (int i = cj::bs.size() - 1; i >= 0; i--){
        if (cj::bs[i] <= v){
            slot = i;
            break;
        }
    }
    vector<int> xseq, yseq;
    int p1 = 0, p2 = 0;
    while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
        if (p1 == cj::big[slot][x].size()){
            if (cj::small[slot][x][p2].second <= v) cj::push(xseq, cj::small[slot][x][p2].first);
            p2++;
        }
        else if (p2 == cj::small[slot][x].size()){
            cj::push(xseq, cj::big[slot][x][p1]);
            p1++;
        }
        else if (cj::h[cj::big[slot][x][p1]] <= cj::h[cj::small[slot][x][p2].first]){
            cj::push(xseq, cj::big[slot][x][p1]);
            p1++;
        }
        else {
            if (cj::small[slot][x][p2].second <= v) cj::push(xseq, cj::small[slot][x][p2].first);
            p2++;
        }
    }
    p1 = 0;
    p2 = 0;
    while (p1 != cj::big[slot][y].size() || p2 != cj::small[slot][y].size()){
        if (p1 == cj::big[slot][y].size()){
            if (cj::small[slot][y][p2].second <= v) cj::push(yseq, cj::small[slot][y][p2].first);
            p2++;
        }
        else if (p2 == cj::small[slot][y].size()){
            cj::push(yseq, cj::big[slot][y][p1]);
            p1++;
        }
        else if (cj::h[cj::big[slot][y][p1]] <= cj::h[cj::small[slot][y][p2].first]){
            cj::push(yseq, cj::big[slot][y][p1]);
            p1++;
        }
        else {
            if (cj::small[slot][y][p2].second <= v) cj::push(yseq, cj::small[slot][y][p2].first);
            p2++;
        }
    }
    if (xseq.empty() || yseq.empty()){
        return 1e9;
    }
    p1 = 0;
    p2 = 0;
    int output = 1e9+7;
    while (p1 < xseq.size() && p2 < yseq.size()){
        output = min(output, abs(cj::h[xseq[p1]] - cj::h[yseq[p2]]));
        if (cj::h[xseq[p1]] <= cj::h[yseq[p2]]){
            p1++;
        }
        else {
            p2++;
        }
    }
    return output;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < cj::bs.size() -1; i++){
      |                     ~~^~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:91:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if (p1 == cj::big[slot][x].size()){
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         else if (p2 == cj::small[slot][x].size()){
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:111:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     while (p1 != cj::big[slot][y].size() || p2 != cj::small[slot][y].size()){
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:111:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     while (p1 != cj::big[slot][y].size() || p2 != cj::small[slot][y].size()){
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if (p1 == cj::big[slot][y].size()){
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         else if (p2 == cj::small[slot][y].size()){
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:135:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     while (p1 < xseq.size() && p2 < yseq.size()){
      |            ~~~^~~~~~~~~~~~~
potion.cpp:135:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     while (p1 < xseq.size() && p2 < yseq.size()){
      |                                ~~~^~~~~~~~~~~~~
potion.cpp:91:30: warning: 'slot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |     while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
      |                              ^

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