結果
問題 | No.2716 Falcon Method |
ユーザー |
|
提出日時 | 2024-04-05 22:43:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,848 ms / 2,000 ms |
コード長 | 2,139 bytes |
コンパイル時間 | 892 ms |
コンパイル使用メモリ | 91,808 KB |
実行使用メモリ | 119,196 KB |
最終ジャッジ日時 | 2024-10-01 02:50:09 |
合計ジャッジ時間 | 19,901 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <iostream> #include <vector> #include <string> using namespace std; using ll = long long; int main () { int N, Q; cin >> N >> Q; string s; cin >> s; int D = 0, R = 0; for (auto c : s) { if (c == 'D') D++; if (c == 'R') R++; } if (D == 0) { for (int i = 0; i < Q; i++) { int H, W, P; cin >> H >> W >> P; cout << (P + W) % N << "\n"; } return 0; } if (R == 0) { for (int i = 0; i < Q; i++) { int H, W, P; cin >> H >> W >> P; cout << (P + H) % N << "\n"; } return 0; } // 両方向でダブリング -> 短い方を採用 const int MAX = 32; vector<vector<ll>> dp_R(N + 1, vector<ll>(MAX)), dp_D(N + 1, vector<ll>(MAX)); // dp_R[i][j] := カウンタiからスタートして、(カウンタiは踏む)右に2^jマス進むために踏むマス数 { int l = 0, r = 0; while (l < N) { if (r < l) r = l; while (true) { if (s[r % N] == 'R') break; r++; } dp_R[l][0] = r - l + 1; l++; } } { int l = 0, r = 0; while (l < N) { if (r < l) r = l; while (true) { if (s[r % N] == 'D') break; r++; } dp_D[l][0] = r - l + 1; l++; } } for (int j = 0; j < MAX - 1; j++) { for (int i = 0; i < N; i++) { dp_R[i][j + 1] = dp_R[(i + dp_R[i][j]) % N][j] + dp_R[i][j]; dp_D[i][j + 1] = dp_D[(i + dp_D[i][j]) % N][j] + dp_D[i][j]; } } for (int i = 0; i < Q; i++) { int H, W, P; cin >> H >> W >> P; ll h = P; ll w = P; for (int j = 0; j < MAX; j++) { if (0 < (H & (1LL << j))) { h += dp_D[h % N][j]; } } for (int j = 0; j < MAX; j++) { if (0 < (W & (1LL << j))) { w += dp_R[w % N][j]; } } cout << min(h, w) % N << "\n"; } }