oj.uz

Submission #1043887

# Submission time Handle Problem Language Result Execution time Memory
1043887 2024-08-05T02:54:04 Z nightfal Comparing Plants (IOI20_plants) C++17
44 / 100
 1020 ms 456644 KB 
// #include "plants.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <utility>
#include <tuple>
#include <algorithm>



// using namespace std;
#define maxVal 1'000'000'001
static std:: vector<int> inc,dec,rank,lz,lzr,reach,reach2;
static std:: vector<std::pair<int,int>> t,tr;
static std:: vector<std::vector<int>> g, gt, rangeLR;
static std:: vector<std::vector<std::vector<int>>> power;

static int l,m,q2,subtask=6;
void print(std::pair<int,int> p) {std::cout << "(" << p.first << "," << p.second << ") "; };
void print(std::vector<int> &v) {for(int elem: v) std::cout << elem << " "; std::cout << std::endl;}
void print(std::vector<std::vector<int>> &v) {for (auto elem: v) print(elem); std::cout << std::endl;}
void print(std::vector<std::pair<int,int>> &v) {for(auto [a,b]: v) std::cout << "(" << a << "," << b << ") ";std::cout << std::endl;}
void print(std::vector<std::vector<std::vector<int>>> &v) {for (auto elem: v) print(elem); std::cout << std::endl;}

std::pair<int,int> update(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int node,int start,int end,int left,int right,int diff) {
    if (left <= start and end <= right) lz[node] += diff;
    if (start!=end) { lz[2*node] += lz[node]; lz[2*node+1] += lz[node];}
    t[node].first += lz[node]; lz[node]=0;
    if (right < start or end < left) return {maxVal,m+1};
    if (left <= start and end <= right) return t[node];

    int mid=(start+end)/2;
    auto ans1  = update(t,lz,2*node,start,mid,left,right,diff);
    auto ans2  = update(t,lz,2*node+1,mid+1,end,left,right,diff);
    auto ans = std::min(ans1,ans2);
    t[node] = std::min(t[2*node],t[2*node+1]);
    return ans;    
}
std::pair<int,int> findMin(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int node, int start, int end, int left, int right) {
    if (start!=end) {lz[2*node] += lz[node]; lz[2*node+1] += lz[node];}
    t[node].first += lz[node]; lz[node]=0;
    if (right < start or end < left) return {maxVal,m+1};
    if (left <= start and end <= right) return t[node];
    
    int mid=(start+end)/2;
    auto min1 = findMin(t,lz,2*node,start,mid,left,right);
    auto min2 = findMin(t,lz,2*node+1,mid+1,end,left,right);
    auto ans = std::min(min1,min2);
    t[node] = std::min(t[2*node],t[2*node+1]);    
    return ans;
}
void segInit(std::vector<int> &r, std::vector<std::pair<int,int>> &t, int node, int start, int end) {
    if (start==end) {t[node]={r[start],start}; return;}
    int mid=(start+end)/2;
    segInit(r,t, 2*node,start,mid);
    segInit(r,t, 2*node+1,mid+1,end);
    t[node] = std::min(t[2*node],t[2*node+1]);
    return;
}
int findPreMinI(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int k,int minI1) {
    if (minI1>0) {
        auto[min2,minI2] = findMin(t,lz,1,0,m-1,std::max(0,minI1-k+1),minI1-1);
        if (min2==0) minI1 = minI2;
    }
    if (minI1-k+1<0) {
        auto[min2,minI2] = findMin(t,lz,1,0,m-1,minI1-k+1+m,m-1);
        if (min2==0) minI1 = minI2;
    }
    return minI1;
}
int computeRank(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int minI1, int k, int ranking) {

    if (rank[minI1]!=m) return ranking;
    int minI2 = findPreMinI(t,lz,k,minI1);

    while (minI2 != minI1) {
        ranking = computeRank(t,lz,minI2,k,ranking); 
        minI2 = findPreMinI(t,lz,k,minI1);
    }
    rank[minI1] = ranking--;
    update(t,lz,1,0,m-1,minI1,minI1,m-1);
    update(t,lz,1,0,m-1,std::max(0,minI1-k+1),minI1-1,-1);
    if (minI1-k+1<0) update(t,lz,1,0,m-1,minI1-k+1+m,m-1,-1);

    return ranking;
}
void reachable(int node, std::vector<std::vector<int>> &g, std::vector<int> &reach) {
    if (node==-1 or reach[node]) return;
    reach[node] = 1;
    for(int elem: g[node])
        reachable(elem,g,reach);
    return;
}
void calPower() {
    int x = m, cnt=0, rounds;
    while (x) {x>>=1; cnt++;}
    rounds = 2*cnt;
    power.resize(rounds,std::vector<std::vector<int>>(m,std::vector<int>(2,-1)));
    for(int j=0; j<m; j++)
        for(int x=0; x<2; x++)
            power[0][j][x] = g[j][x];
    
    for (int i=1; i<rounds; i++)
        for(int j=0; j<m; j++)
            for(int x=0; x<2; x++)
                if (power[i-1][j][x] == -1) 
                    power[i][j][x] = -1;
                else if (power[i-1][power[i-1][j][x]][x]==-1) 
                    power[i][j][x] = power[i-1][j][x];
                else power[i][j][x] = power[i-1][power[i-1][j][x]][x];

    rangeLR = power[rounds-1];
   
    // std::cout << "rank: "<<std::endl; print(rank);
    // std::cout << "power: "<<std::endl; print(power);
    // std::cout << "rangeLR: "<<std::endl; print(rangeLR);


}
void calReachability(int k) {
    tr.resize(4*m); lzr.resize(4*m);
    std::vector<std::pair<int,int>> rankInv;
    for(int i=0; i<m; i++) {rank[i] = -rank[i]; rankInv.push_back({rank[i],i}); }
    sort(rankInv.begin(),rankInv.end());
    segInit(rank,tr,1,0,m-1);

    g.resize(m,std::vector<int>(2,-1)); gt.resize(m);
    
    for(auto [val,i]: rankInv) {
        std::pair<int,int> temp1, temp2;
        temp1 = temp2 = findMin(tr,lzr,1,0,m-1,std::max(0,i-k+1),i-1);
        if (i-k+1<0) temp2 = findMin(tr,lzr,1,0,m-1,i-k+1+m,m-1);
        temp1 = std::min(temp1,temp2);
        if (temp1.first <=0) {g[i][0] = temp1.second;gt[temp1.second].push_back(i);}

        temp1 = temp2 = findMin(tr,lzr,1,0,m-1,i+1,std::min(m-1,i+k-1));
        if (i+k-1>m-1) temp2 = findMin(tr,lzr,1,0,m-1,0,i+k-1-m);
        temp1 = std::min(temp1,temp2);
        if (temp1.first <= 0) {g[i][1] = temp1.second;gt[temp1.second].push_back(i);}
        update(tr,lzr,1,0,m-1,i,i,m);
    }

    calPower();

    // subtask 6
    // reach.resize(m); reach2.resize(m);
    // reachable(0,g,reach);
    // reachable(0,gt,reach2);
    return;
}
void init6(int k, std::vector<int> &r) {
    int n = r.size(); 
    t.resize(4*n); lz.resize(4*n); 
    segInit(r,t,1,0,n-1);
    rank.resize(n,n);
    int ranking = n-1;
    while (ranking >=0) {
        auto [min1,minI1] = findMin(t,lz,1,0,n-1,0,n-1);
        ranking = computeRank(t,lz,minI1,k,ranking);
    }
    calReachability(k);
    return;
}
void transClosure(int n, int k) {
    for (int i=0; i<n; i++)
        for(int j=i-k+1+n; j<=i+k-1+n; j++)
            if (rank[j%n]<rank[i%n]) g[i][j%n]=1;
        for(int x=0; x<n; x++)
        for (int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                g[i][j] = g[i][j] or g[i][x] and g[x][j];
    
    return;
}
void init5(int k, std::vector<int> &r) {
    int n = r.size(); 
    t.resize(4*n); lz.resize(4*n); g.resize(n,std::vector<int>(n));
    segInit(r,t,1,0,n-1);
    rank.resize(n,n);
    int ranking = n-1;
    while (ranking >=0) {
        auto [min1,minI1] = findMin(t,lz,1,0,n-1,0,n-1);
        ranking = computeRank(t,lz,minI1,k,ranking);
    }
    transClosure(n, k);
    return;    
}
void init4(int k, std::vector<int> &r) {
    int n = r.size(); 
    t.resize(4*n); lz.resize(4*n);
    segInit(r,t,1,0,n-1);
    rank.resize(n,n);

    int ranking = n-1;
    while (ranking >=0) {
        auto [min1,minI1] = findMin(t,lz,1,0,n-1,0,n-1);
        ranking = computeRank(t,lz,minI1,k,ranking);
    }
    return;
}
void init3(int k, std::vector<int> &r) {
    int n = r.size(); 
    t.resize(4*n); lz.resize(4*n);
    segInit(r,t,1,0,n-1);
    rank.resize(n,n);

    for(int i=n-1; i>=0; i--) {
        auto [min1,minI1] = findMin(t,lz,1,0,n-1,0,n-1);
        int min2=1, minI2=minI1;
        int min3=1, minI3=minI1;
        if (minI1>0) std::tie(min2,minI2) = findMin(t,lz,1,0,n-1,std::max(0,minI1-(n-k)),minI1-1);
        if (minI1-(n-k)<0) std::tie(min3,minI3) = findMin(t,lz,1,0,n-1,minI1-(n-k)+n,n-1);
        if (min3==0) minI1=minI3;
        else if (min2==0) minI1=minI2;
        rank[minI1] = i;
        update(t,lz,1,0,n-1,minI1,minI1,n-1);
        update(t,lz,1,0,n-1,std::max(0,minI1-k+1),minI1-1,-1);
        if (minI1-k+1<0) update(t,lz,1,0,n-1,minI1-k+1+n,n-1,-1);
    }
    return;
}
int findMax(int k, std::vector<int> &r) {
    int i=2*m-1;
    while (r[i%m]!=0) {i--;}
    int j = i-1;
    while (j > i-k) {
        if (r[j%m]==0) i = j; 
        j--;
    }
    for(int j=i; j>i-k; j--) r[j%m]--;
    return i%m;
}
void init2(int k, std::vector<int> &r) {
    int n = r.size();
    rank.resize(n);
    for(int i=n-1; i>=0; i--)
        rank[findMax(k,r)] = i;   
    return;
}
void init1(int k, std::vector<int> &r) {
    int n = r.size();
    inc.resize(n); dec.resize(n);
    for(int i=0; i<n; i++) {inc[i] = dec[i] = i;}
    int s,incVal,decVal;
    for(s=2*n-1; s>=0; s--) {
        if (r[s%n]==0) incVal = s;
        else decVal = s;
        inc[s%n] = incVal; dec[s%n] = decVal;
    }
    return;
}
void init(int k, std::vector<int> r) {
    int n = r.size(); 
    m=n; l=k;

    // for(int elem: x)
    //     if (elem !=0) {subtask==-1; break;}
    init6(k,r); return;
	if(k==2) init1(k, r);
    else if(n<=5000 and 2*k>n) init2(k, r);
    else if(2*k>n) init3(k,r);
    else if (n<=300 and q2 <= n*(n-1)/2) init5(k,r);
    else if (subtask==6) init6(k,r);
    else init4(k,r);
	return;
}
int compare(int x, int y) {
    int left = rangeLR[x][0], right = rangeLR[x][1];
    if(left!=-1 && (left <= y && y < x || !(x < y && y < left))) return 1;
    if(right!=-1 && (x < y && y <= right || !(right < y && y < x))) return 1;
    return 0;

        // if(left!=-1) {
        //     if (left > x) left-=m;
        //     if (y > x) y-=m;
        //     if(left <= y) return 1;
        // }
        // if (right!=-1) {
        //     if (right < x) right+=m;
        //     if (y < x) y+=m;
        //     if(y <= right) return 1;
        // }
        // return 0;
}
int compare_plants7(int x, int y) {
    int left,right;
    if (-rank[x]>-rank[y]) return compare(x,y);
    else return -compare(y,x);
}
int compare_plants6(int x, int y) {
    if (reach[y]) return 1;
    else if (reach2[y]) return -1;
    else return 0;
}
int compare_plants5(int x, int y) {
    if (g[x][y]) return 1;
    else if (g[y][x]) return -1;
    else return 0;
}
int compare_plants2(int x, int y) {
    if (rank[x]>rank[y]) return 1;
    else return -1;
}
int compare_plants1(int x, int y) {
    if (y <= dec[x] or x+m <= inc[y]) return 1;
    else if (y <= inc[x] or x+m <= dec[y]) return -1;
	return 0;
}
int compare_plants(int x, int y) {
    return compare_plants7(x,y);
  	if(l==2) return compare_plants1(x,y);
    else if(m<=5000 and 2*l>m) return compare_plants2(x,y);
    else if(2*l>m) return compare_plants2(x,y);
    if (m<=300 and q2 <= m*(m-1)/2) return compare_plants5(x,y);
    else if (subtask==6)  return compare_plants6(x,y);
    else return compare_plants2(x,y);
	return 0;
}

Compilation message

plants.cpp: In function 'void transClosure(int, int)':
plants.cpp:166:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  166 |     for (int i=0; i<n; i++)
      |     ^~~
plants.cpp:169:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  169 |         for(int x=0; x<n; x++)
      |         ^~~
plants.cpp:172:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  172 |                 g[i][j] = g[i][j] or g[i][x] and g[x][j];
plants.cpp: In function 'int compare(int, int)':
plants.cpp:270:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  270 |     if(left!=-1 && (left <= y && y < x || !(x < y && y < left))) return 1;
      |                     ~~~~~~~~~~^~~~~~~~
plants.cpp:271:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  271 |     if(right!=-1 && (x < y && y <= right || !(right < y && y < x))) return 1;
      |                      ~~~~~~^~~~~~~~~~~~~
plants.cpp: In function 'int compare_plants7(int, int)':
plants.cpp:287:9: warning: unused variable 'left' [-Wunused-variable]
  287 |     int left,right;
      |         ^~~~
plants.cpp:287:14: warning: unused variable 'right' [-Wunused-variable]
  287 |     int left,right;
      |              ^~~~~
plants.cpp: In function 'void init1(int, std::vector<int>&)':
plants.cpp:249:37: warning: 'decVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  249 |         inc[s%n] = incVal; dec[s%n] = decVal;
plants.cpp:249:18: warning: 'incVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  249 |         inc[s%n] = incVal; dec[s%n] = decVal;

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1628 KB Output is correct
7 Correct 44 ms 11652 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 3 ms 1624 KB Output is correct
10 Correct 43 ms 11556 KB Output is correct
11 Correct 40 ms 11536 KB Output is correct
12 Correct 38 ms 11792 KB Output is correct
13 Correct 42 ms 11604 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1628 KB Output is correct
7 Correct 44 ms 11652 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 3 ms 1624 KB Output is correct
10 Correct 43 ms 11556 KB Output is correct
11 Correct 40 ms 11536 KB Output is correct
12 Correct 38 ms 11792 KB Output is correct
13 Correct 42 ms 11604 KB Output is correct
14 Correct 109 ms 41560 KB Output is correct
15 Correct 967 ms 452976 KB Output is correct
16 Correct 104 ms 43860 KB Output is correct
17 Correct 1020 ms 456624 KB Output is correct
18 Correct 706 ms 456132 KB Output is correct
19 Correct 707 ms 456644 KB Output is correct
20 Correct 957 ms 456644 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 32 ms 6036 KB Output is correct
4 Correct 624 ms 454500 KB Output is correct
5 Correct 764 ms 456132 KB Output is correct
6 Correct 862 ms 456204 KB Output is correct
7 Correct 951 ms 456384 KB Output is correct
8 Correct 958 ms 456560 KB Output is correct
9 Correct 665 ms 456092 KB Output is correct
10 Correct 693 ms 455900 KB Output is correct
11 Correct 580 ms 455668 KB Output is correct
12 Correct 640 ms 455876 KB Output is correct
13 Correct 704 ms 456048 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -