제출 #628753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628753		kingmoshe	송신탑 (IOI22_towers)	C++17	23 / 100	4093 ms	14808 KiB

towers

//#include "towers.h"

#include <vector>
#include <iostream>
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
std::vector<int> real_h(0);
vvi maxi(0);
int total_maxi = 0;
bool is_interesting = false;


void init_maxi(int N) {
    maxi.resize(N, vi(0));
    for (int i = 0; i < N; i++) {
        maxi[i].push_back(i);
    }
    int size = 2;
    while (size <= N) {
        for (int i = 0; i < N; i += size) {
            int value = maxi[i][maxi[i].size() - 1];
            int next_place = i + (size / 2);
            if (next_place < N) {
                int other_value = maxi[next_place][maxi[next_place].size() - 1];
                if (real_h[other_value] > real_h[value]) {
                    value = other_value;
                }
            }
            maxi[i].push_back(value);
        }
        size *= 2;
    }
}

void init_is_interesting(int N) {
    bool going_up = true;
    for (int i = 1; i < N; i++) {
        if (real_h[i] < real_h[i - 1]) {
            if (going_up) {
                going_up = false;
            }
            else {
                return;
            }
        }
        else {
            if (!going_up) {
                return;
            }
        }
    }
    is_interesting = true;
}
void init(int N, std::vector<int> H) {
    real_h.resize(N);
    for (int i = 0; i < N; i++) {
        real_h[i] = H[i];
        if (real_h[i] > total_maxi) {
            total_maxi = real_h[i];
        }
    }
    init_maxi(N);

}

int get_max_id2(int l, int r) {
    if (l == r) {
        return l;
    }
    int size = 1;
    for (int i = 1; i < maxi[l].size(); i++) {
        if (l + size + size - 1 > r) {
            int temp_maxi = maxi[l][i - 1];
            if (l + size - 1 == r) {
                return temp_maxi;
            }
            else {
                int other_res = get_max_id2(l + size, r);
                if (real_h[other_res] > real_h[temp_maxi]) {
                    return other_res;
                }
                return temp_maxi;
            }
        }
        size *= 2;
    }
    int temp_maxi = maxi[l][maxi[l].size() - 1];
    if (l + size - 1 == r) {
        return temp_maxi;
    }
    else {
        int other_res = get_max_id2(l + size, r);
        if (real_h[other_res] > real_h[temp_maxi]) {
            return other_res;
        }
        return temp_maxi;
    }
}

int get_max_id(int l, int r) {
    int max_result = real_h[l];
    int max_id =l;
    for (int i = l + 1; i <= r; i++) {
        if (real_h[i] > max_result) {
            max_result = real_h[i];
            max_id = i;
        }
    }
    return max_id;
}

int get_min_id(int l, int r) {
    int min_result= real_h[l];
    int min_id =l;
    for (int i = l + 1; i <= r; i++) {
        if (real_h[i] < min_result) {
            min_result = real_h[i];
            min_id = i;
        }
    }
    return min_id;
}

int max_towers_interesting(int l, int r, int d) {
    int max_id = get_max_id2(l, r);
    if (l == r) {
        return 1;
    }
    if (real_h[max_id] != total_maxi) {
        return 1;
    }
    if (max_id == l) {
        return 1;
    }
    if (max_id == r) {
        return 1;
    }
    return 2;
}
int max_towers2(int l, int r, int d, int max_possible_value) {
    if (l > r) {
        return 0;
    }
    if (l == r) {
        if (real_h[l] <= max_possible_value) {
            return 1;
        }
        return 0;
    }
    if (l + 1 == r) {
        if (real_h[l] <= max_possible_value || real_h[l + 1] <= max_possible_value) {
            return 1;
        }
        return 0;
    }
    int max_id = get_max_id2(l, r);
    int left_value = max_towers2(l, max_id - 1, d, real_h[max_id] - d);
    int right_value = max_towers2(max_id + 1, r, d, real_h[max_id] - d);
    if (left_value + right_value == 0) {
        int min_id = get_min_id(l, r);
        if (real_h[min_id] <= max_possible_value) {
            return 1;
        }
    }
    return left_value + right_value;
}
int max_towers(int L, int R, int D) {
    if (is_interesting) {
        return max_towers_interesting(L, R, D);
    }
    return max_towers2(L, R, D, total_maxi);
}

/*int main() {
    init(7, std::vector<int>{10, 20, 60, 40, 50, 30, 70});
    std::cout << max_towers(1, 5, 10) << std::endl;
    std::cout << max_towers(2, 2, 100) << std::endl;
    std::cout << max_towers(0, 6, 17) << std::endl;

}//*/

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In function 'int get_max_id2(int, int)':
towers.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 1; i < maxi[l].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23