結果
問題 | No.2716 Falcon Method |
ユーザー |
![]() |
提出日時 | 2024-04-08 16:44:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 520 ms / 2,000 ms |
コード長 | 1,625 bytes |
コンパイル時間 | 1,648 ms |
コンパイル使用メモリ | 197,036 KB |
最終ジャッジ日時 | 2025-02-20 23:08:00 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);//x=Hまたはy=Wにするまでに必要な操作の回数//x=Hにするための操作回数とy=Wにするための操作回数の最小値ll N, Q, H, W, P, ok, ng, mid, ans;string S;cin >> N >> Q >> S;vector<ll> D(N+1), R(N+1);for (int i=1; i<=N; i++){if (S[i-1] == 'D') D[i]++;else R[i]++;D[i] += D[i-1];R[i] += R[i-1];}//01234//DDRRRauto f=[&](ll p, ll n, vector<ll> &v){n += p;ll res=0, q, r;//カウンターpから始まってn回押すまでの間に(D or R)がいくつ存在するか?q = n / N;r = n % N;res += v[N] * q;res += v[r];res -= v[p];return res;};//f(p, X, D) >= Hを満たす最小のXfor (int i=0; i<Q; i++){ans = 1e18;cin >> H >> W >> P;//Hについてif (D[N] != 0){ok = N*H; ng = 0;while(ok-ng>1){mid = (ok+ng)/2;if (f(P, mid, D) >= H) ok = mid;else ng = mid;}ans = min(ans, ok);}//Wについてif (R[N] != 0){ok = N*W; ng = 0;while(ok-ng>1){mid = (ok+ng)/2;if (f(P, mid, R) >= W) ok = mid;else ng = mid;}ans = min(ans, ok);}cout << (ans+P)%N << endl;}return 0;}