제출 #468451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468451		gavgav	Fountain (eJOI20_fountain)	C++17	0 / 100	108 ms	5948 KiB

fountain

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(){
    /*
     * Get dates about fountain
     * Creating array in witch every number denotes index of the nearest number witch greater than this reservoir.
     * Indexes in this array means number of reservoir.
     */
    int height, queries;
    scanf("%d%d", &height, &queries);
    int diameters[height], next_grater[height + 1], capacities[height + 1];
    capacities[height - 1] = 0;
    fill(next_grater, next_grater + height + 1, -1);
    stack <int> meowmeow;
    for (int i = 0; i < height; i++){
        scanf("%d%hd", &diameters[i], &capacities[i]);
        while (!meowmeow.empty() && diameters[i] > diameters[meowmeow.top()]){
            next_grater[meowmeow.top()] = i;
            meowmeow.pop();
        }
        meowmeow.push(i);
    }
    while (!meowmeow.empty()){
        next_grater[meowmeow.top()] = height;
        meowmeow.pop();
    }
    /*
     * Creating of any possible water path.
     */
    int indexes[height], last = 0;
    fill(indexes, indexes + height, -1);
    vector <int> lengths;
    vector <vector <int>> ways;
    for (int i = 0; i < height;){
        ways.push_back(vector <int> {});
        lengths.push_back(-1);
        for (int j = i; j + 1;){
            ways[last].push_back(j);
            lengths[last]++;
            indexes[j] = last;
            if (j + 1 == next_grater[j]){
                i++;
            }
            j = next_grater[j];
        }
        i++;
        while (i < height && indexes[i] != - 1){
            i++;
        }
        last++;
    }
    /*
     * Creating postfix sums array.
     */
    for (int i = height; i > -1; i--){
        if (next_grater[i] != -1){
            capacities[i] += capacities[next_grater[i]];
        }
    }
    /*
     * Get queries and by binary search print answer.
     */
    int volume, level, left, right, middle, answer;
    while (queries--){
        scanf("%d %d", &level, &volume);
        level--;
        left = 0, right = lengths[indexes[level]];
        while (left - right < 1){
            middle = (left + right) / 2;
            if (volume > capacities[level] - capacities[ways[indexes[level]][middle]]){
                answer = ways[indexes[level]][middle] + 1;
                left = middle + 1;
            }
            else {
                right = middle - 1;
            }
        }
        printf("%d\n", answer % (height + 1));
    }
}

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

fountain.cpp: In function 'int main()':
fountain.cpp:18:20: warning: format '%hd' expects argument of type 'short int*', but argument 3 has type 'int*' [-Wformat=]
   18 |         scanf("%d%hd", &diameters[i], &capacities[i]);
      |                  ~~^                  ~~~~~~~~~~~~~~
      |                    |                  |
      |                    short int*         int*
      |                  %d
fountain.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d%d", &height, &queries);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%hd", &diameters[i], &capacities[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d %d", &level, &volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:80:15: warning: 'answer' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |         printf("%d\n", answer % (height + 1));
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40