oj.uz

답안 #436803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
436803 2021-06-25T00:55:11 Z edenooo 사탕 분배 (IOI21_candies) C++17
0 / 100
 162 ms 12008 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

#define INF 1234567890
#define ll long long

int N, Q;
ll A[200201], mn[200201], mx[200201];

vector<int> distribute_candies(vector<int> C, vector<int> L,
                                    vector<int> R, vector<int> V) {
    N = C.size(); Q = L.size();
    ll sum = 0;
    A[0] = 0;
    for(int i=0; i<Q; i++)
    {
        sum += V[i];
        A[i+1] = sum;
    }
    mn[Q+1] = INF, mx[Q+1] = -INF;
    for(int i=Q; i>=0; i--)
    {
        mn[i] = min(mn[i+1], A[i]);
        mx[i] = max(mx[i+1], A[i]);
    }

    vector<int> res(N);
    for(int i=0; i<N; i++)
    {
        // 합이 C[i] 이상인 최단 suffix 찾기
        int lo = -1, hi = Q; // lo : 가능, hi : 불가능
        for(int j=0; j<18; j++)
        {
            int mid = lo+hi>>1;
            if (mid == -1) break;
            else if (mx[mid]-mn[mid] >= C[i]) lo = mid;
            else hi = mid;
        }
        if (lo == -1) res[i] = A[Q]-mn[0];
        else if (mn[lo] != mn[lo+1]) res[i] = C[i]-(mx[lo]-A[Q]);
        else res[i] = A[Q]-mn[lo];
    }
    return res;
}

// int main() {}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:36:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |             int mid = lo+hi>>1;
      |                       ~~^~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 143 ms 12008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 69 ms 9696 KB Output is correct
4 Correct 77 ms 2760 KB Output is correct
5 Correct 162 ms 12004 KB Output is correct
6 Correct 148 ms 11948 KB Output is correct
7 Incorrect 146 ms 11972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -