Submission #320423

#	Time	Username	Problem	Language	Result	Execution time	Memory
320423		arujbansal	Labels (NOI20_labels)	C++17	100 / 100	77 ms	6792 KiB

Labels

#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int N = 3e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;
int n;
int a[N];

bool check(int x) {

    for (int i = 1; i < n; i++) {
        x = x + a[i - 1];
        if (x > n) return false;
    }

    return true;
}

signed main() {
    FAST_IO;
#ifdef arujbansal_local
    setIO("input.txt", "output.txt");
#endif

    cin >> n;
    for (int i = 0; i < n - 1; i++) cin >> a[i];

    int lo = 1, hi = n, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {
            ans = max(ans, mid);
            lo = mid + 1;
        } else hi = mid - 1;
    }

    vi seq(n);
    seq[0] = ans;

    bool one = (seq[0] == 1);

    for (int i = 1; i < n; i++) {
        seq[i] = seq[i - 1] + a[i - 1];
        if (seq[i] == 1) one = true;
    }

    if (one)
        for (const auto &x : seq) cout << x << " ";
    else cout << -1;
}

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