結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
|
提出日時 | 2018-10-10 13:48:59 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,505 bytes |
コンパイル時間 | 923 ms |
コンパイル使用メモリ | 64,240 KB |
実行使用メモリ | 8,832 KB |
最終ジャッジ日時 | 2024-10-12 17:14:32 |
合計ジャッジ時間 | 8,198 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 3 TLE * 1 -- * 8 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(void) { int N; cin >> N; vector<int> M(N + 1); for(int i = 1; i <= N; i++) { cin >> M[i]; } vector<int> V(N + 1, 0); for(int i = 1; i <= N; i++) { if(0 < M[i] - i) { V[i] = 1; } else if(0 > M[i] - i) { V[i] = -1; } } int maxt = 0; for(int i = 1; i <= N; i++) { maxt = max(maxt, abs(M[i] - i)); } int ans = 0; for(int t = 1; t <= maxt; t++) { vector<int> NCatStay(30001, 0); vector<int> NCatComeFromL(30001, 0); vector<int> NCatComeFromR(30001, 0); cerr << t << endl; for(int i = 1; i <= N; i++) { if(0 == V[i]) { cerr << i << ' ' << M[i] << endl; NCatStay[M[i]]++; } else { int pos = i + V[i] * t; cerr << i << ' ' << pos << endl; if(V[i] > 0) { NCatComeFromL[pos]++; } else { NCatComeFromR[pos]++; } if(M[i] == pos) { V[i] = 0; } } } for(int i = 1; i < 100; i++) { int NCatCome = NCatComeFromL[i] + NCatComeFromR[i]; ans += NCatStay[i] * NCatCome; ans += NCatCome * (NCatCome - 1) / 2; cerr << i << ' ' << NCatStay[i] << ' ' << NCatCome; if(i > 1) { ans += NCatComeFromR[i - 1] * NCatComeFromL[i]; cerr << ' ' << NCatComeFromR[i - 1] << ' ' << NCatComeFromL[i]; } cerr << ' ' << ans << endl; } } cout << ans << endl; return 0; }