oj.uz

Submission #866123

# Submission time Handle Problem Language Result Execution time Memory
866123 2023-10-25T12:49:10 Z danikoynov The Potion of Great Power (CEOI20_potion) C++14
31 / 100
 3000 ms 38864 KB 
#include<bits/stdc++.h>

using namespace std;
    


const int maxn = 2e5 + 10;
int n, h[maxn];

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

const int maxq = 50010;

pair < int, int > edge[maxn];
unordered_set < int > act[maxn];
int u;
void curseChanges(int U, int A[], int B[]) 
{
    u = U;
    for (int i = 0; i < U; i ++) 
    {
        edge[i] = {A[i], B[i]};
    }
    
    
    for (int j = 0; j < U; j ++)
    {
        int a = edge[j].first, b = edge[j].second;
        if (act[a].find(b) == act[a].end())
        {
            act[a].insert(b);    
            act[b].insert(a);
        }
        else
        {
            act[a].erase(b);
            act[b].erase(a);
        }
    }   

}

int question(int x, int y, int v) 
{
    if (v == u)
    {
        
        vector < int > hx, hy;
        for (int cur : act[x])
            hx.push_back(h[cur]);
        for (int cur : act[y])
            hy.push_back(h[cur]);

        sort(hx.begin(), hx.end());
        sort(hy.begin(), hy.end());
        ///cout << "here " << hx.size() << " " << hy.size() << endl;
        int ans = 1e9;
        int pt = 0;
        for (int i = 0; i < hx.size(); i ++)
        {
            while(pt < hy.size() && hy[pt] <= hx[i])
                pt ++;

            if (pt != 0)
                ans = min(ans, abs(hx[i] - hy[pt - 1]));
            if (pt != hy.size())
                ans = min(ans, abs(hx[i] - hy[pt]));
        }
        return ans;
    }
    set < int > sx, sy;

    for (int i = 0; i < v; i ++)
    {
        int a = edge[i].first;
        int b = edge[i].second;

        if (a == x)
        {
            if (sx.find(b) == sx.end())
                sx.insert(b);
            else
                sx.erase(b);
        }
        
        if (b == x)
        {
            if (sx.find(a) == sx.end())
                sx.insert(a);
            else
                sx.erase(a);
        }

        if (a == y)
        {
            if (sy.find(b) == sy.end())
                sy.insert(b);
            else
                sy.erase(b);
        }
        
        if (b == y)
        {
            if (sy.find(a) == sy.end())
                sy.insert(a);
            else
                sy.erase(a);
        }
    }

    if (sx.empty() && sy.empty())
        return 1e9;

    int ans = 1e9;
    for (int a : sx)
        for (int b : sy)
            ans = min(ans, abs(h[a] - h[b]));
    
    return ans;
    
}
/**
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 11
*/

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 0; i < hx.size(); i ++)
      |                         ~~^~~~~~~~~~~
potion.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             while(pt < hy.size() && hy[pt] <= hx[i])
      |                   ~~~^~~~~~~~~~~
potion.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             if (pt != hy.size())
      |                 ~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 5 ms 12888 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 13 ms 14044 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 38864 KB Output is correct
2 Correct 229 ms 38404 KB Output is correct
3 Correct 86 ms 15172 KB Output is correct
4 Correct 1102 ms 22992 KB Output is correct
5 Correct 499 ms 31988 KB Output is correct
6 Correct 2561 ms 28656 KB Output is correct
7 Correct 376 ms 29184 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 14680 KB Output is correct
2 Correct 570 ms 13656 KB Output is correct
3 Correct 2782 ms 13232 KB Output is correct
4 Execution timed out 3015 ms 14424 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 5 ms 12888 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 13 ms 14044 KB Output is correct
6 Correct 239 ms 38864 KB Output is correct
7 Correct 229 ms 38404 KB Output is correct
8 Correct 86 ms 15172 KB Output is correct
9 Correct 1102 ms 22992 KB Output is correct
10 Correct 499 ms 31988 KB Output is correct
11 Correct 2561 ms 28656 KB Output is correct
12 Correct 376 ms 29184 KB Output is correct
13 Execution timed out 3045 ms 38516 KB Time limit exceeded
14 Halted 0 ms 0 KB -