Submission #2148006
Source Code Expand
#include <bits/stdc++.h> using namespace std; using VS = vector<string>; using LL = long long; using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; using PLL = pair<LL, LL>; using VL = vector<LL>; using VVL = vector<VL>; #define ALL(a) begin((a)),end((a)) #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(a) int((a).size()) #define SORT(c) sort(ALL((c))) #define RSORT(c) sort(RALL((c))) #define UNIQ(c) (c).erase(unique(ALL((c))), end((c))) #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++) #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--) #define debug(x) cerr << #x << ": " << x << endl const int INF = 1e9; const LL LINF = 1e16; const LL MOD = 1000000007; const double PI = acos(-1.0); int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 }; /* ----- 2018/03/02 Problem: 010_agc_b / Link: https://agc010.contest.atcoder.jp/tasks/agc010_b?lang=en ----- */ /* ------問題------ N 個の箱が円環状に並んでおり、i 番目の箱には Ai 個の石が入っています。 以下の操作を繰り返して、全ての石を取り除くことができるか判定してください。 箱を一か所選ぶ。それを i 番目としたとき、1 から N の各 j に対して、i+j 番目の箱から石をちょうど j 個取り除く。 ただし、N+k 番目と表される箱は k 番目の箱と同一視するものとする。 各操作において、取り除きたい個数の石がない箱があるときは、その操作を行えないことに注意してください。 -----問題ここまで----- */ /* -----解説等----- わからないので悲しくなって階差をとると、数字に規則性を感じる。 階差を取ることで得られる情報として、数列を生成するごとに+1がn-1回、-Nが1回加算される。 このことからこれが成り立っているかを確認すれば良い。 条件は”階差数列の値が数列を生成するのに必要な回数以下、かつ先の関係が成立している” ----解説ここまで---- */ LL N; LL ans = 0LL; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> N; VI a(2 * N); LL sum = 0; FOR(i, 0, N) { cin >> a[i]; a[i + N] = a[i]; sum += a[i]; } ans = 1; LL k = sum / (N*(N + 1) / 2); if (k*(N*(N + 1) / 2) != sum)ans = 0; FOR(i, 0, N) { int diff = a[i + 1] - a[i]; if (k - diff < 0 || ((k - diff) % N != 0))ans = 0; } if (ans) { cout << "YES" << endl; } else cout << "NO" << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Boxes |
User | vjudge3 |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2685 Byte |
Status | AC |
Exec Time | 12 ms |
Memory | 1024 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 11 ms | 1024 KB |
in10.txt | AC | 2 ms | 384 KB |
in11.txt | AC | 12 ms | 1024 KB |
in12.txt | AC | 12 ms | 1024 KB |
in13.txt | AC | 10 ms | 896 KB |
in14.txt | AC | 1 ms | 256 KB |
in15.txt | AC | 1 ms | 256 KB |
in16.txt | AC | 1 ms | 256 KB |
in17.txt | AC | 1 ms | 256 KB |
in18.txt | AC | 1 ms | 256 KB |
in19.txt | AC | 1 ms | 256 KB |
in2.txt | AC | 12 ms | 1024 KB |
in20.txt | AC | 1 ms | 256 KB |
in21.txt | AC | 12 ms | 1024 KB |
in22.txt | AC | 12 ms | 1024 KB |
in23.txt | AC | 12 ms | 1024 KB |
in24.txt | AC | 2 ms | 256 KB |
in25.txt | AC | 2 ms | 384 KB |
in26.txt | AC | 12 ms | 1024 KB |
in27.txt | AC | 12 ms | 1024 KB |
in3.txt | AC | 12 ms | 1024 KB |
in4.txt | AC | 12 ms | 1024 KB |
in5.txt | AC | 12 ms | 1024 KB |
in6.txt | AC | 12 ms | 1024 KB |
in7.txt | AC | 12 ms | 1024 KB |
in8.txt | AC | 2 ms | 384 KB |
in9.txt | AC | 2 ms | 384 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |