結果
問題 | No.2716 Falcon Method |
ユーザー |
|
提出日時 | 2024-04-05 21:51:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 1,104 bytes |
コンパイル時間 | 2,113 ms |
コンパイル使用メモリ | 197,476 KB |
最終ジャッジ日時 | 2025-02-20 21:13:04 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,Q; cin >> N >> Q; string s; cin >> s; int D = 0,R = 0; for(auto c : s){ if(c == 'D') D++; else R++; } s += s; vector<int> sumd(2*N),sumr(2*N); for(int i=0; i<2*N; i++){ if(s.at(i) == 'D') sumd.at(i)++; else sumr.at(i)++; } for(int i=1; i<2*N; i++) sumd.at(i) += sumd.at(i-1),sumr.at(i) += sumr.at(i-1); while(Q--){ int h,w,p; cin >> h >> w >> p; int hl = 2e9,wl = 2e9; if(D) hl = (h-1)/D; if(R) wl = (w-1)/R; h -= min(hl,wl)*D; w -= min(hl,wl)*R; int ph = 0,pw = 0; if(p) ph = sumd.at(p-1),pw = sumr.at(p-1); int low = p-1,high = p+N; while(high-low > 1){ int mid = (high+low)/2; int nowh = sumd.at(mid)-ph,noww = sumr.at(mid)-pw; if(nowh >= h || noww >= w) high = mid; else low = mid; } high++; cout << high%N << endl; } }