結果
問題 | No.2716 Falcon Method |
ユーザー |
![]() |
提出日時 | 2024-04-05 21:50:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 948 ms / 2,000 ms |
コード長 | 1,273 bytes |
コンパイル時間 | 1,993 ms |
コンパイル使用メモリ | 198,004 KB |
最終ジャッジ日時 | 2025-02-20 21:12:15 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9 + 10; const ll INFL = 4e18; int main() { int N, Q; cin >> N >> Q; string S; cin >> S; vector<vector<int>> cnt(N + 1, vector<int>(2, 0)); for (int i = 0; i < N; i++) { cnt[i + 1][0] = cnt[i][0]; cnt[i + 1][1] = cnt[i][1]; if (S[i] == 'D') { cnt[i + 1][0]++; } else { cnt[i + 1][1]++; } } while (Q--) { ll H, W, P; cin >> H >> W >> P; ll lo = 0, hi = 1ll * INF * 3; while (hi - lo > 1) { ll mid = (lo + hi) / 2; ll cycle = mid / N; ll rem = (P + mid) % N; ll nx = 0, ny = 0; nx += cnt[N][0] * cycle; ny += cnt[N][1] * cycle; if (P <= rem) { nx += cnt[rem][0] - cnt[P][0]; ny += cnt[rem][1] - cnt[P][1]; } else { nx += cnt[N][0] - cnt[P][0] + cnt[rem][0]; ny += cnt[N][1] - cnt[P][1] + cnt[rem][1]; } if (nx < H && ny < W) { lo = mid; } else { hi = mid; } } cout << (P + hi) % N << '\n'; } }