oj.uz

답안 #1044872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1044872 2024-08-05T14:14:29 Z nightfal 식물 비교 (IOI20_plants) C++17
19 / 100
 1121 ms 281028 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,rounds;
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;
}
bool inRangeLeft(int z, int y, int left) {return left!=-1 && (y < z && (z < left || left <= y) || z < y && (z < left && left <= y));}
bool inRangeRight(int z, int y, int right) {return right!=-1 && (z < y && (right < z || y <= right) || y < z && (y <= right && right < z));}

int compare(int x, int y) {
    int left, i=0, z=x;
    while(true) {
        left = power[i][z][0];
        if(left==-1 || inRangeLeft(z,y,left)) break;
        i++;
    }
    for(int j=i-1; j>=0; j--) {
        left = power[j][z][0];
        if (left!=-1 && !inRangeLeft(z,y,left)) z = left; 
    }
    left = power[0][z][0];
    if (left!=-1 && inRangeLeft(z,y,left) && -rank[z]>-rank[y]) return 1;

    int right; 
    i=0; z= x;
    while(true) {
        right = power[i][z][1];
        if(right==-1 || inRangeRight(z,y,right)) break;
        i++;
    }
    for(int j=i-1; j>=0; j--) {
        right = power[j][z][1];
        if(right!=-1 && !inRangeRight(z,y,right)) z = right;
    }
    right = power[0][z][1];
    if(right!=-1 && inRangeRight(z,y,right) && -rank[z]>-rank[y]) return 1;

    return 0;
}
int compare_plants7(int x, int y) {
    // std::cout<< std::endl << "x:" << x << " y:" << y << " " << std::endl;
    int ans = compare(x,y);
    if (ans) return ans;
    else return -compare(y,x);
}
void calPower() {
    int x = m-1, cnt=1;
    while (x) {x>>=1; cnt++;}
    cnt++;
    power.resize(cnt,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<cnt; 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 power[i][j][x] = power[i-1][power[i-1][j][x]][x];
            }
    // 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_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 'bool inRangeLeft(int, int, int)':
plants.cpp:93:69: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   93 | bool inRangeLeft(int z, int y, int left) {return left!=-1 && (y < z && (z < left || left <= y) || z < y && (z < left && left <= y));}
      |                                                               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
plants.cpp: In function 'bool inRangeRight(int, int, int)':
plants.cpp:94:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 | bool inRangeRight(int z, int y, int right) {return right!=-1 && (z < y && (right < z || y <= right) || y < z && (y <= right && right < z));}
      |                                                                  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
plants.cpp: In function 'void transClosure(int, int)':
plants.cpp:196:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  196 |     for (int i=0; i<n; i++)
      |     ^~~
plants.cpp:199:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  199 |         for(int x=0; x<n; x++)
      |         ^~~
plants.cpp:202:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  202 |                 g[i][j] = g[i][j] or g[i][x] and g[x][j];
plants.cpp: At global scope:
plants.cpp:17:29: warning: 'rounds' defined but not used [-Wunused-variable]
   17 | static int l,m,q2,subtask=6,rounds;
      |                             ^~~~~~
plants.cpp: In function 'void init1(int, std::vector<int>&)':
plants.cpp:279:37: warning: 'decVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  279 |         inc[s%n] = incVal; dec[s%n] = decVal;
plants.cpp:279:18: warning: 'incVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  279 |         inc[s%n] = incVal; dec[s%n] = decVal;

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 33 ms 3916 KB Output is correct
7 Correct 132 ms 28496 KB Output is correct
8 Correct 540 ms 279088 KB Output is correct
9 Correct 594 ms 279132 KB Output is correct
10 Correct 711 ms 279164 KB Output is correct
11 Correct 755 ms 279308 KB Output is correct
12 Correct 822 ms 279236 KB Output is correct
13 Correct 890 ms 279344 KB Output is correct
14 Correct 1069 ms 279636 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 68 ms 9832 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 4 ms 1352 KB Output is correct
10 Correct 67 ms 10012 KB Output is correct
11 Correct 90 ms 9784 KB Output is correct
12 Correct 119 ms 10040 KB Output is correct
13 Correct 64 ms 9828 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 68 ms 9832 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 4 ms 1352 KB Output is correct
10 Correct 67 ms 10012 KB Output is correct
11 Correct 90 ms 9784 KB Output is correct
12 Correct 119 ms 10040 KB Output is correct
13 Correct 64 ms 9828 KB Output is correct
14 Correct 133 ms 28368 KB Output is correct
15 Correct 994 ms 279916 KB Output is correct
16 Incorrect 131 ms 28624 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 77 ms 6488 KB Output is correct
4 Correct 1121 ms 281028 KB Output is correct
5 Incorrect 1069 ms 279744 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 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 604 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 16 ms 1628 KB Output is correct
8 Incorrect 10 ms 1628 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 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 436 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 731 ms 278712 KB Output is correct
7 Correct 890 ms 278980 KB Output is correct
8 Correct 840 ms 278972 KB Output is correct
9 Correct 1024 ms 279092 KB Output is correct
10 Correct 760 ms 278916 KB Output is correct
11 Correct 797 ms 279032 KB Output is correct
12 Correct 830 ms 280800 KB Output is correct
13 Correct 902 ms 278980 KB Output is correct
14 Incorrect 911 ms 279108 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 33 ms 3916 KB Output is correct
7 Correct 132 ms 28496 KB Output is correct
8 Correct 540 ms 279088 KB Output is correct
9 Correct 594 ms 279132 KB Output is correct
10 Correct 711 ms 279164 KB Output is correct
11 Correct 755 ms 279308 KB Output is correct
12 Correct 822 ms 279236 KB Output is correct
13 Correct 890 ms 279344 KB Output is correct
14 Correct 1069 ms 279636 KB Output is correct
15 Correct 1 ms 432 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 3 ms 1372 KB Output is correct
21 Correct 68 ms 9832 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 4 ms 1352 KB Output is correct
24 Correct 67 ms 10012 KB Output is correct
25 Correct 90 ms 9784 KB Output is correct
26 Correct 119 ms 10040 KB Output is correct
27 Correct 64 ms 9828 KB Output is correct
28 Correct 133 ms 28368 KB Output is correct
29 Correct 994 ms 279916 KB Output is correct
30 Incorrect 131 ms 28624 KB Output isn't correct
31 Halted 0 ms 0 KB -