Submission #643561

#	Time	Username	Problem	Language	Result	Execution time	Memory
643561		Kripton	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	1827 ms	16952 KiB

potion

#include <bits/stdc++.h>
using namespace std;
int h[100001];
vector <pair <int,int>> v[100001];
vector <int> v1[100001];
bool cmp(int a,int b)
{
    return h[a]<h[b];
}
int vec1[501],vec2[501];
int cnt1,cnt2;
bool ap[100001];
int n,d;
void init(int N,int D,int H[])
{
    n=N;
    d=D;
    for(int i=0; i<n; i++)
        h[i]=H[i];
}
void curseChanges(int U,int A[],int B[])
{
    for(int i=0; i<U; i++)
    {
        v[A[i]].push_back({B[i],i+1});
        v[B[i]].push_back({A[i],i+1});
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<v[i].size(); j++)
        {
            if(!ap[v[i][j].first])
            {
                ap[v[i][j].first]=1;
                   v1[i].push_back(v[i][j].first);
            }
        }
        for(int j=0; j<v[i].size(); j++)
            ap[v[i][j].first]=0;
        sort(v1[i].begin(),v1[i].end(),cmp);
    }
}
int question(int x,int y,int zi)
{
    int min1=1e9,i,j;
    int cnt1=cnt2=0;
    for(j=0; j<v[x].size(); j++)
    {
        if(v[x][j].second>zi)
            break;
        ap[v[x][j].first]^=1;
    }
    for(j=0; j<v1[x].size(); j++)
        if(ap[v1[x][j]])
            vec1[++cnt1]=h[v1[x][j]];
    for(j=0; j<v1[x].size(); j++)
        ap[v1[x][j]]=0;
    for(j=0; j<v[y].size(); j++)
    {
        if(v[y][j].second>zi)
            break;
        ap[v[y][j].first]^=1;
    }
    for(j=0; j<v1[y].size(); j++)
        if(ap[v1[y][j]])
            vec2[++cnt2]=h[v1[y][j]];
    for(j=0; j<v1[y].size(); j++)
        ap[v1[y][j]]=0;
    if(cnt1==0||cnt2==0)
        return min1;
    else
    {
        int t=1;
        for(int s=1; s<=cnt1; s++)
        {
            while(t<cnt2&&vec2[t]<vec1[s])
                t++;
            if(vec2[t]==vec1[s])
            {
                min1=0;
                break;
            }
            if(t==1)
                min1=min(min1,abs(vec2[t]-vec1[s]));
            else
                min1=min(min1,min(abs(vec2[t]-vec1[s]),abs(vec2[t-1]-vec1[s])));
        }
        return min1;
    }
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int j=0; j<v[i].size(); j++)
      |                      ~^~~~~~~~~~~~
potion.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j=0; j<v[i].size(); j++)
      |                      ~^~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(j=0; j<v[x].size(); j++)
      |              ~^~~~~~~~~~~~
potion.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(j=0; j<v1[x].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(j=0; j<v1[x].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(j=0; j<v[y].size(); j++)
      |              ~^~~~~~~~~~~~
potion.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(j=0; j<v1[y].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(j=0; j<v1[y].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:45:18: warning: unused variable 'i' [-Wunused-variable]
   45 |     int min1=1e9,i,j;
      |                  ^

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