結果
問題 | No.2716 Falcon Method |
ユーザー |
![]() |
提出日時 | 2024-04-05 22:02:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 1,260 bytes |
コンパイル時間 | 2,304 ms |
コンパイル使用メモリ | 194,236 KB |
最終ジャッジ日時 | 2025-02-20 21:23:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define mp make_pair using ll = long long; using pii = pair<int,int>; constexpr int mod = 998244353; constexpr int inf = 0x3f3f3f3f; constexpr int N = 4e5 + 10; int n, Q, d[N], r[N]; string s; int calc(int *a, int m, int p){ int r = m % a[n-1]; if(r == 0) r = a[n-1]; if(p != 0) r += a[p-1]; return lower_bound(a, a+n*2, r) - a + 1; } ll f(int *a, int m, int p){ if(m % a[n-1] == 0){ return calc(a, m, p) - p + 1ll * (m / a[n-1] - 1) * n; } return calc(a, m, p) - p + 1ll * m / a[n-1] * n; } int solve(int h, int w, int p){ if(d[n-1] == 0){ return calc(r, w, p) % n; } if(r[n-1] == 0){ return calc(d, h, p) % n; } ll c1 = f(d, h, p); ll c2 = f(r, w, p); if(c1 < c2) return calc(d, h, p) % n; return calc(r, w, p) % n; } void _main(){ cin >> n >> Q >> s; for(int i=0; i<n; ++i){ if(s[i] == 'D'){ d[i] = d[i+n] = 1; } else { r[i] = r[i+n] = 1; } } for(int i=1; i<n*2; ++i){ d[i] += d[i-1]; r[i] += r[i-1]; } int h, w, p; while(Q--){ cin >> h >> w >> p; cout << solve(h, w, p) << '\n'; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); _main(); return 0; }