Submission #1372998

---

Source Code Expand

/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 1e5 + 10;

int n, a[MAXN], id;

pii rec(int i){
    int ans, mn = INF, cnt = 0, mni;
    for (int j = 0; j < n; ++j){
        a[(i + j) % n] -= j + 1;
        if (a[(i + j) % n] < 0)
            return {0, 0};
        if (a[(i + j) % n] < mn)
            mn = a[(i + j) % n], mni = (i + j) % n;
        if (a[(i + j) % n] == 0)
            ++cnt;
    }
    if (cnt == n)
        return {1, -1};
    return {2, mni};
}

int main(){
    #ifndef SAKO
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    #endif // SAKO
    ios_base::sync_with_stdio(0);

    cin >> n;
    for (int i = 0; i < n; ++i){
        cin >> a[i];
        if (a[i] < a[id])
            id = i;
    }
    while (true){
        pii p = rec(id);
//        if (id == 4){
//            for (int i = 0; i < n; ++i)
//                cout << a[i] << " ";
//            cout << "\n";
//        }
        if (p.fr == 1){
            cout << "YES";
            return 0;
        }
        if (p.fr == 0){
            cout << "NO";
            return 0;
        }
        id = p.sc;
    }

    return 0;
}

Submission Info

Judge Result