Submission #861710

#	Time	Username	Problem	Language	Result	Execution time	Memory
861710		wakandaaa	Labels (NOI20_labels)	C++17	100 / 100	49 ms	10832 KiB

Labels

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;

template<class X, class Y>
bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}

template<class X, class Y>
bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}

template<class X, class Y>
bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}

int n;
int a[N], d[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i < n; ++i)
        cin >> d[i];

    int s = 0;
    int dmax = 0, dmin = 0;
    for (int i = 1; i < n; ++i) {
        s += d[i];
        dmax = max(dmax, s);
        dmin = min(dmin, s);
    }

    if (dmax - dmin != n - 1)
        return cout << -1, 0;

    a[1] = n - dmax;
    for (int i = 1; i < n; ++i) {
        a[i + 1] = a[i] + d[i];
    }

    for (int i = 1; i <= n; ++i)
        cout << a[i] << ' ';

    return 0;
}

/*

if a_max - a_min < n - 1, it's impossible to recover a
so a_max - a_min = n - 1 -> a_min = 1, a_max = n

let d'[k] = d[1] + ... + d[k] = a[k + 1] - a[1]
d[max] - d[min] = a[max] - a[min]

d'[max] = a[max] - a[1] = n - a[1] -> a[1] = n - d[max]

*/

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 18 / 18
• Subtask 5: 35 / 35