結果

問題 No.1509 Swap!!
コンテスト
ユーザー southsidesamurai65-prog
提出日時 2026-08-18 01:12:32
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,167 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,473 ms
コンパイル使用メモリ 172,164 KB
実行使用メモリ 9,300 KB
最終ジャッジ日時 2026-08-18 01:12:42
合計ジャッジ時間 7,697 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
typedef long long ll;
typedef tuple<ll,ll,ll> tlll;
//能交换任意两个相邻肯定就能实现全部序列，要实现全部序列也得能交换任意两个相邻
//最难的就是最中间的两个互换，因为两边空间更大
//扩展欧几里得算法
tlll check(ll a,ll b){
    if(a<b) swap(a,b);
    ll q=a/b;ll r=a-q*b;
    if(r==0) return make_tuple(b,1,q-1);
    auto sub=check(b,r);
    return make_tuple(get<0>(sub),get<2>(sub),get<1>(sub)-get<2>(sub)*q);
}
int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        ll n,a,b;
        cin>>n>>a>>b;
        if(a==1||b==1) {cout<<"YES"<<endl;continue;}
        if(a<b) swap(a,b);
        auto rst=check(a,b);
        if(get<0>(rst)!=1) {cout<<"NO"<<endl;continue;}
        //中间最多往前走N/2
        ll x=get<1>(rst)%b;ll y=get<2>(rst)%a;
        //知道问题了，前面系数有一个模的问题，我们要找最小的
        if(x>0&&x*a>n/2&&(y+a)*b>n/2) {cout<<"NO"<<endl;continue;}
        if(y>0&&y*b>n/2&&(x+b)*a>n/2) {cout<<"NO"<<endl;continue;}
        cout<<"YES"<<endl;
    }
    return 0;
}
0