oj.uz

답안 #1042430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042430 2024-08-03T04:28:12 Z nightfal 식물 비교 (IOI20_plants) C++14
19 / 100
 131 ms 5976 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].second += lz[node]; lz[node]=0;
    if (right < start or end < left) return {m+1,maxVal};
    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].second += 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:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [a,b]: v)
      |              ^
plants.cpp: In function 'void init3(int, std::vector<int>&)':
plants.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         auto [min1,minI1] = findMin(1,0,n-1,0,n-1);
      |              ^
plants.cpp: In function 'void init1(int, std::vector<int>&)':
plants.cpp:112:37: warning: 'decVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |         inc[s%n] = incVal; dec[s%n] = decVal;
plants.cpp:112:18: warning: 'incVal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |         inc[s%n] = incVal; dec[s%n] = decVal;

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 25 ms 3264 KB Output is correct
7 Correct 29 ms 3436 KB Output is correct
8 Correct 42 ms 5976 KB Output is correct
9 Correct 39 ms 5884 KB Output is correct
10 Correct 39 ms 5724 KB Output is correct
11 Correct 40 ms 5716 KB Output is correct
12 Correct 42 ms 5716 KB Output is correct
13 Correct 37 ms 5716 KB Output is correct
14 Correct 40 ms 5884 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 4 ms 500 KB Output is correct
7 Correct 113 ms 3092 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 115 ms 3092 KB Output is correct
11 Correct 87 ms 3156 KB Output is correct
12 Correct 89 ms 3344 KB Output is correct
13 Correct 131 ms 3152 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 4 ms 500 KB Output is correct
7 Correct 113 ms 3092 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 115 ms 3092 KB Output is correct
11 Correct 87 ms 3156 KB Output is correct
12 Correct 89 ms 3344 KB Output is correct
13 Correct 131 ms 3152 KB Output is correct
14 Incorrect 35 ms 4436 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 344 KB Execution killed with signal 11
3 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 412 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 25 ms 3264 KB Output is correct
7 Correct 29 ms 3436 KB Output is correct
8 Correct 42 ms 5976 KB Output is correct
9 Correct 39 ms 5884 KB Output is correct
10 Correct 39 ms 5724 KB Output is correct
11 Correct 40 ms 5716 KB Output is correct
12 Correct 42 ms 5716 KB Output is correct
13 Correct 37 ms 5716 KB Output is correct
14 Correct 40 ms 5884 KB Output is correct
15 Correct 0 ms 344 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 0 ms 348 KB Output is correct
20 Correct 4 ms 500 KB Output is correct
21 Correct 113 ms 3092 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 5 ms 348 KB Output is correct
24 Correct 115 ms 3092 KB Output is correct
25 Correct 87 ms 3156 KB Output is correct
26 Correct 89 ms 3344 KB Output is correct
27 Correct 131 ms 3152 KB Output is correct
28 Incorrect 35 ms 4436 KB Output isn't correct
29 Halted 0 ms 0 KB -