oj.uz

Submission #1042443

# Submission time Handle Problem Language Result Execution time Memory
1042443 2024-08-03T04:33:04 Z nightfal Comparing Plants (IOI20_plants) C++14
32 / 100
 331 ms 18280 KB 
// #include "plants.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>


#include <utility>
#include <tuple>
// using namespace std;
#define maxVal 1'000'000'001
static std:: vector<int> inc,dec,rank,lz;
static std:: vector<std::pair<int,int>> t;
static int l,m;
// void print(std::vector<int> &v) {for(int elem: v) std::cout << elem << " "; std::cout << std::endl;}
void print(std::vector<int> &v) {for(int elem: v) std::cout << 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;
    return;
}
std::pair<int,int> update(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 min1  = update(2*node,start,mid,left,right,diff);
    auto min2  = update(2*node+1,mid+1,end,left,right,diff);
    auto ans = min1<min2? min1:min2;
    t[node] = t[2*node]<t[2*node+1]? t[2*node]:t[2*node+1];    
    return ans;    
}
std::pair<int,int> findMin(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(2*node,start,mid,left,right);
    auto min2 = findMin(2*node+1,mid+1,end,left,right);
    auto ans = min1<min2? min1:min2;
    t[node] = t[2*node]<t[2*node+1]? t[2*node]:t[2*node+1];    
    return ans;
}
void segInit(int node, int start, int end, std::vector<int> &r) {
    if (start==end) {t[node]={r[start],start}; return;}
    int mid=(start+end)/2;
    segInit(2*node,start,mid,r);
    segInit(2*node+1,mid+1,end,r);
    t[node] = t[2*node]<t[2*node+1]? t[2*node]:t[2*node+1];
    return;
}
void init3(int k, std::vector<int> &r) {
    int n = r.size(); 
    t.resize(4*n); lz.resize(4*n);
    segInit(1,0,n-1,r);
    rank.resize(n);
    for(int i=n-1; i>=0; i--) {
        auto [min1,minI1] = findMin(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(1,0,n-1,std::max(0,minI1-(n-k)),minI1-1);
        if (minI1-(n-k)<0) std::tie(min3,minI3) = findMin(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(1,0,n-1,minI1,minI1,n-1);
        update(1,0,n-1,std::max(0,minI1-k+1),minI1-1,-1);
        if (minI1-k+1<0) update(1,0,n-1,minI1-k+1+n,n-1,-1);
    }
    return;
}
// int compare_plants3(int x, int y) {
//     if (rank[x]>rank[y]) return 1;
//     else return -1;
// }
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;
}
int compare_plants2(int x, int y) {
    if (rank[x]>rank[y]) return 1;
    else return -1;
}
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;
}
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;
}
void init(int k, std::vector<int> r) {
    int n = r.size(); 
    m=n; l=k;
	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);
	return;
}
int compare_plants(int x, int 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);
    return compare_plants2(x,y);
	return 0;
}

Compilation message

plants.cpp: In function 'void print(std::vector<std::pair<int, int> >&)':
plants.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for(auto [a,b]: v)
      |              ^
plants.cpp: In function 'void init3(int, std::vector<int>&)':
plants.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         auto [min1,minI1] = findMin(1,0,n-1,0,n-1);
      |              ^
plants.cpp: In function 'void init1(int, std::vector<int>&)':
plants.cpp:113:37: warning: 'decVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |         inc[s%n] = incVal; dec[s%n] = decVal;
plants.cpp:113:18: warning: 'incVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |         inc[s%n] = incVal; dec[s%n] = decVal;

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 31 ms 3164 KB Output is correct
7 Correct 37 ms 3408 KB Output is correct
8 Correct 40 ms 5720 KB Output is correct
9 Correct 44 ms 5712 KB Output is correct
10 Correct 44 ms 5712 KB Output is correct
11 Correct 44 ms 5876 KB Output is correct
12 Correct 39 ms 5768 KB Output is correct
13 Correct 45 ms 5892 KB Output is correct
14 Correct 38 ms 5716 KB Output is correct

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 1 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 130 ms 3112 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 130 ms 3324 KB Output is correct
11 Correct 87 ms 3152 KB Output is correct
12 Correct 107 ms 3344 KB Output is correct
13 Correct 140 ms 3108 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 1 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 130 ms 3112 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 130 ms 3324 KB Output is correct
11 Correct 87 ms 3152 KB Output is correct
12 Correct 107 ms 3344 KB Output is correct
13 Correct 140 ms 3108 KB Output is correct
14 Correct 82 ms 4436 KB Output is correct
15 Correct 331 ms 18000 KB Output is correct
16 Correct 54 ms 6504 KB Output is correct
17 Correct 309 ms 18004 KB Output is correct
18 Correct 225 ms 17744 KB Output is correct
19 Correct 210 ms 18280 KB Output is correct
20 Correct 262 ms 18260 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 0 ms 344 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

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 Correct 0 ms 348 KB Output is correct
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 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 Runtime error 0 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 31 ms 3164 KB Output is correct
7 Correct 37 ms 3408 KB Output is correct
8 Correct 40 ms 5720 KB Output is correct
9 Correct 44 ms 5712 KB Output is correct
10 Correct 44 ms 5712 KB Output is correct
11 Correct 44 ms 5876 KB Output is correct
12 Correct 39 ms 5768 KB Output is correct
13 Correct 45 ms 5892 KB Output is correct
14 Correct 38 ms 5716 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 4 ms 348 KB Output is correct
21 Correct 130 ms 3112 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 4 ms 348 KB Output is correct
24 Correct 130 ms 3324 KB Output is correct
25 Correct 87 ms 3152 KB Output is correct
26 Correct 107 ms 3344 KB Output is correct
27 Correct 140 ms 3108 KB Output is correct
28 Correct 82 ms 4436 KB Output is correct
29 Correct 331 ms 18000 KB Output is correct
30 Correct 54 ms 6504 KB Output is correct
31 Correct 309 ms 18004 KB Output is correct
32 Correct 225 ms 17744 KB Output is correct
33 Correct 210 ms 18280 KB Output is correct
34 Correct 262 ms 18260 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Runtime error 0 ms 344 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -