結果
問題 | No.2716 Falcon Method |
ユーザー |
|
提出日時 | 2024-04-05 21:45:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 2,303 bytes |
コンパイル時間 | 2,175 ms |
コンパイル使用メモリ | 197,700 KB |
最終ジャッジ日時 | 2025-02-20 21:08:16 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); void Solve() { int n, q; cin >> n >> q; string s; cin >> s; vector <int> p1(n + 1, 0), p2(n + 1, 0); for (int i = 1; i <= n; i++){ p1[i] = p1[i - 1] + (s[i - 1] == 'D'); p2[i] = p2[i - 1] + (s[i - 1] == 'R'); } while (q--){ int h, w, p; cin >> h >> w >> p; p++; if (p1[n] == 0){ int steps = w - 1; p += steps; cout << (p % n) << "\n"; continue; } if (p2[n] == 0){ int steps = h - 1; p += steps; cout << (p % n) << "\n"; continue; } // can you go whole route? int x = 0, y = 0; if (x + p1[n] - p1[p - 1] < h && y + p2[n] - p2[p - 1] < w){ x += p1[n] - p1[p - 1]; y += p2[n] - p2[p - 1]; int d1 = h - x - 1; int d2 = w - y - 1; int g1 = d1 / p1[n]; int g2 = d2 / p2[n]; int g = min(g1, g2); x += g * p1[n]; y += g * p2[n]; p = 1; } // cout << x << " " << y << " " << p << "\n"; int l = p, r = n; while (l != r){ int mid = (l + r) / 2; if (x + p1[mid] - p1[p - 1] < h && y + p2[mid] - p2[p - 1] < w){ l = mid + 1; } else { r = mid; } } cout << (l % n) << "\n"; } } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // freopen("in", "r", stdin); // freopen("out", "w", stdout); // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }