Submission #946131

#	Time	Username	Problem	Language	Result	Execution time	Memory
946131		berr	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	1752 ms	33196 KiB

potion

#include <bits/stdc++.h>
using namespace std;
 
int n, d;
vector<int> h;
vector<vector<array<int, 2>>> a;
vector<vector<array<int, 2>>> op;
vector<vector<vector<int>>> b;
 
void init(int N, int D, int H[]){
 
    n = N; d = D;
    a.resize(n);
    b.resize(n);
    op.resize(n);
    for(int i=0; i<n; i++) h.push_back(H[i]);
    vector<int> emp;
    for(int i=0; i<n; i++){
        a[i].push_back({0, 0});
        b[i].push_back(emp);
    }
}
 
void curseChanges(int U, int A[], int B[]){
    for(int i=1; i<=U; i++){
        op[B[i-1]].push_back({i, A[i-1]});
        op[A[i-1]].push_back({i, B[i-1]});
    }
 
    for(int i=0; i<n; i++){
        vector<int> st;
        for(int j=0; j<op[i].size(); j++){
            st.push_back(op[i][j][1]);
            if(j%50) continue;
 
                vector<int>ar;
               
                sort(st.begin(), st.end(), [&](int x, int y){
                    if(h[x]!=h[y]) return h[x]<h[y];
                    return x<y;
                });
                int k=1;
                for(int l=1; l<st.size(); l++){
                    if(st[l]==st[l-1]) k++;
                    else{
                        if(k%2==1){
                            ar.push_back(st[l-1]);
                        }
                        k=1;
                    }
                }
 
                if(k%2==1){
                    ar.push_back(st.back());
                }
 
                a[i].push_back({op[i][j][0], j});
                b[i].push_back(ar);
                st = ar;
 
            }            
            
        
    }
}
 
 
int question(int x, int y, int v){
 
    int posx=lower_bound(a[x].begin(), a[x].end(), (array<int, 2>){v+1, 0})-a[x].begin()-1;
    int posy=lower_bound(a[y].begin(), a[y].end(),(array<int, 2>){v+1, 0})-a[y].begin()-1;
 
 
    vector<int> xx=b[x][posx], yy=b[y][posy], xr, yr;
 
    for(int i=a[x][posx][1]+1; i<op[x].size()&&op[x][i][0]<=v; i++){
        xx.push_back(op[x][i][1]);
    }
 
    for(int i=a[y][posy][1]+1; i<op[y].size()&&op[y][i][0]<=v; i++){
        yy.push_back(op[y][i][1]);
    }
    sort(xx.begin(), xx.end(), [&](int x, int y){
 
        if(h[x]!=h[y]) return h[x]<h[y];
        return x<y;
    });
 
    sort(yy.begin(), yy.end(), [&](int x, int y){
        if(h[x]!=h[y]) return h[x]<h[y];
        return x<y;
    });
 
 
    int k=1;
    for(int l=1; l<xx.size(); l++){
        if(xx[l]==xx[l-1]) k++;
        else{
            if(k%2==1){
                xr.push_back(xx[l-1]);
            }
            k=1;
        }
    }
 
    if(k%2==1&&xx.size()){
        xr.push_back(xx.back());
    }
    k=1;
    for(int l=1; l<yy.size(); l++){
        if(yy[l]==yy[l-1]) k++;
        else{
            if(k%2==1){
                yr.push_back(yy[l-1]);
            }
            k=1;
        }
    }
 
    if(k%2==1&&yy.size()){
        yr.push_back(yy.back());
    }
 
 
    int itrx=0, itry=0;
 
    int ans = 1e9;
    while(1){
        if(itrx>=xr.size()) break;
        if(itry>=yr.size()) break;
       
        ans=min(ans, abs(h[xr[itrx]]-h[yr[itry]]));
        if(h[xr[itrx]] < h[yr[itry]]) itrx++;
        else itry++;
 
    }
    return ans;
    return 1;
}/*
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;
    }
  }
  cout<<(float)(clock())/1000.0<<"\n";
 
  if (correct) {
    std::cout << "Correct." << std::endl;
  } else std::cout << "Incorrect." << std::endl;
    return 0;
 
}*/

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j=0; j<op[i].size(); j++){
      |                      ~^~~~~~~~~~~~~
potion.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 for(int l=1; l<st.size(); l++){
      |                              ~^~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:76:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=a[x][posx][1]+1; i<op[x].size()&&op[x][i][0]<=v; i++){
      |                                ~^~~~~~~~~~~~~
potion.cpp:80:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=a[y][posy][1]+1; i<op[y].size()&&op[y][i][0]<=v; i++){
      |                                ~^~~~~~~~~~~~~
potion.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int l=1; l<xx.size(); l++){
      |                  ~^~~~~~~~~~
potion.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int l=1; l<yy.size(); l++){
      |                  ~^~~~~~~~~~
potion.cpp:129:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         if(itrx>=xr.size()) break;
      |            ~~~~^~~~~~~~~~~
potion.cpp:130:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         if(itry>=yr.size()) break;
      |            ~~~~^~~~~~~~~~~

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