oj.uz

Submission #640358

# Submission time Handle Problem Language Result Execution time Memory
640358 2022-09-14T10:49:09 Z lis05st Comparing Plants (IOI20_plants) C++17
19 / 100
 674 ms 5848 KB 
#ifdef LIS05ST
    #define _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG_PEDANTIC
#endif
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt")
#include"plants.h"
#include"bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;

const int NMAX=2e5;
int pref[NMAX+5];
int n,k;

int get(int l,int r){
    return pref[r]-pref[l-1];
}
bool one(int l,int r){
    return get(l,r)==r-l+1;
}
bool zero(int l,int r){
    return get(l,r)==0;
}
vector<int>h;
int id(int x){
    return (x%n+n)%n;
}
void init(int K, std::vector<int> R){
    n=R.size();h.resize(n);
    k=K;
    for(int i=0;i<n;i++)pref[i+1]=pref[i]+R[i];

    
    if(n<=5000)for(int step=n;step>=1;step--){
        int sum=0;
        for(int m=1;m<k;m++)sum+=R[id(0-m)]==0;
        for(int i=0;i<n;i++){
            if(R[i]==0&&sum==0){
                h[i]=step;
                for(int m=0;m<k;m++)R[id(i-m)]--;
                break;
            }
            sum+=R[i]==0;
            sum-=R[id(i-k+1)]==0;
        }
    }
};
int compare_plants(int x, int y){
    if(k==2){
        x++,y++;
        if(zero(x,y-1))return 1;
        if(one(1,x-1)&&one(y,n))return 1;
        if(one(x,y-1))return -1;
        if(zero(1,x-1)&&zero(y,n))return -1;
        return 0;
    }
    if(h[x]>h[y])return 1;
    if(h[x]<h[y])return -1;
    return 0;
}

#define MULTITESTS false
void solve(int testCase){

}

           
//   x     y


void precalc(){

}
/*
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    precalc();
    int t=1;
    if(MULTITESTS)cin>>t;
    for(int i=1;i<=t;i++){
        auto t1=clock();
        solve(i);
        auto t2=clock();
        float delta=t2-t1;
        delta/=CLOCKS_PER_SEC;
        #ifdef LIS05ST
        cout<<"("<<i<<")------------"<<fixed<<setprecision(2)<<delta<<"s\n";
        #endif
    }
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 48 ms 3124 KB Output is correct
7 Correct 53 ms 3396 KB Output is correct
8 Correct 81 ms 5708 KB Output is correct
9 Correct 65 ms 5760 KB Output is correct
10 Correct 65 ms 5756 KB Output is correct
11 Correct 70 ms 5744 KB Output is correct
12 Correct 72 ms 5748 KB Output is correct
13 Correct 61 ms 5848 KB Output is correct
14 Correct 61 ms 5708 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 340 KB Output is correct
7 Correct 575 ms 3116 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 22 ms 380 KB Output is correct
10 Correct 591 ms 3124 KB Output is correct
11 Correct 445 ms 3120 KB Output is correct
12 Correct 408 ms 3248 KB Output is correct
13 Correct 674 ms 3116 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 340 KB Output is correct
7 Correct 575 ms 3116 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 22 ms 380 KB Output is correct
10 Correct 591 ms 3124 KB Output is correct
11 Correct 445 ms 3120 KB Output is correct
12 Correct 408 ms 3248 KB Output is correct
13 Correct 674 ms 3116 KB Output is correct
14 Incorrect 46 ms 3296 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 48 ms 3124 KB Output is correct
7 Correct 53 ms 3396 KB Output is correct
8 Correct 81 ms 5708 KB Output is correct
9 Correct 65 ms 5760 KB Output is correct
10 Correct 65 ms 5756 KB Output is correct
11 Correct 70 ms 5744 KB Output is correct
12 Correct 72 ms 5748 KB Output is correct
13 Correct 61 ms 5848 KB Output is correct
14 Correct 61 ms 5708 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 25 ms 340 KB Output is correct
21 Correct 575 ms 3116 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 22 ms 380 KB Output is correct
24 Correct 591 ms 3124 KB Output is correct
25 Correct 445 ms 3120 KB Output is correct
26 Correct 408 ms 3248 KB Output is correct
27 Correct 674 ms 3116 KB Output is correct
28 Incorrect 46 ms 3296 KB Output isn't correct
29 Halted 0 ms 0 KB -