제출 #1129372

#제출 시각아이디문제언어결과실행 시간메모리
1129372GrayNice sequence (IZhO18_sequence)C++20
15 / 100
6 ms948 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 1e9+7;

void solve(){
    ll n, m; cin >> n >> m;
    ll mx = max(m, n), mn = min(m, n);
    if (mx%mn==0){
        cout << mx-1 << ln;
        for (ll i=0; i<mx-1; i++){
            cout << (mn==n?-1:1) << " ";
        }
        cout << ln;
    }else{
        ll mid = (mx/mn+1)*mn-mx;
        ll nmid = mn-mid;
        // cout << mn-mid << " : " << mid << ln;
        vector<ll> res;
        if (nmid>mid){
            /*
            should:
            midv*mid>nmidv*nmid
            midv*mid<nmidv*nmid*2
            midv*(mx/mn)*mid<nmidv*((mx/mn)+1)*nmid
            (mx/mn)*mid/((mx/mn+1)*nmid)<nmidv/midv

            mid/(nmid)>nmidv/midv>(mx/mn)*mid/((mx/mn+1)*nmid)
            mid -> 3
            nmid -> 1
            3/1>nmidv/midv>3/2
            nmidv -> 6
            midv -> 3
            */
            ll nmidv = mid+mid*(mx/mn), midv = nmid+(mx/mn+1)*nmid;

            for (ll i=0; i<mx/mn; i++){
                for (ll j=0; j<mn-mid; j++){
                    res.push_back(nmidv);
                }
                for (ll j=0; j<mid; j++){
                    res.push_back(-midv);
                }
            }
            for (ll i=0; i<mn-mid; i++){
                res.push_back(nmidv);
            }
        }else{
            {
                /*
                should:
                midv*mid>nmidv*nmid
                midv*(mx/mn+1)*mid<nmidv*((mx/mn))*nmid
                (mx/mn+1)*mid/((mx/mn)*nmid)<nmidv/midv

                mid/(nmid)>nmidv/midv>(mx/mn+1)*mid/((mx/mn)*nmid)
                mid -> 3
                nmid -> 1
                3/1>nmidv/midv>3/2
                nmidv -> 6
                midv -> 3
                */
                ll nmidv = mid+mid*(mx/mn+1), midv = nmid+(mx/mn)*nmid;

                for (ll i=0; i<mx/mn; i++){
                    for (ll j=0; j<mid; j++){
                        res.push_back(midv);
                    }
                    for (ll j=0; j<mn-mid; j++){
                        res.push_back(-nmidv);
                    }
                }
                for (ll i=0; i<mid; i++){
                    res.push_back(midv);
                }
            }
        }
        if (mn!=n){
            for (auto &ch:res) ch=-ch;
        }
        cout << res.size() << ln;
        for (auto ch:res) cout << ch << " ";
        cout << ln;
    }
}
/*
5 5 -4 -4 -4 5 5
nmidv/midv<mid/(mn-mid)
midv*mid<nmidv*(mn-mid)*2

mid/((nm-mid)*2)<nmidv/midv<mid/(mn-mid)
19 4 x 10 2

*/
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...