제출 #811151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
811151		penguinman	사탕 분배 (IOI21_candies)	C++17	0 / 100	181 ms	27192 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int N = c.size();
    ll Q = l.size();
    vi max(Q+1), min(Q+1), sum(Q+1);
    per(i,Q,1){
        sum[i-1] = sum[i]+v[i-1];
        max[i-1] = std::max(max[i], sum[i-1]);
        min[i-1] = std::min(min[i], sum[i-1]);
    }
    vi left(N,-1), right(N,Q);
    while(true){
        vi mid(N);
        bool flg = true;
        vii query(Q+1);
        rep(i,0,N){
            if(left[i]+1 < right[i]){
                mid[i] = (left[i]+right[i])/2;
                query[mid[i]].pb(i);
                flg = false;
            }
        }
        if(flg) break;
        per(i,Q,0){
            for(auto el: query[i]){
                if(c[el] <= max[i]-min[i]) left[el] = mid[el];
                else right[el] = mid[el];
            }
        }
    }
    vector<int> ans(N);
    rep(i,0,N){
        if(left[i] == -1) ans[i] = sum[0];
        else{
            if(v[left[i]] > 0){
                ans[i] = c[i]+min[left[i]];
            }
            else{
                ans[i] = max[left[i]];
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33