제출 #1129393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129393		Gray	Nice sequence (IZhO18_sequence)	C++20	15 / 100	6 ms	952 KiB

sequence

#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 = 1;
        ll nmid = mn-mid;
        // cout << mn-mid << " : " << mid << ln;
        vector<ll> res;
        ll nmidv = mid+mid*(mx/mn), midv = nmid+(mx/mn+1)*nmid;
        nmidv/=__gcd(nmidv, midv);
        midv/=__gcd(nmidv, midv);
            // cout << nmidv << " " << midv << ln;
            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);
            }
        if (mn!=n){
            for (auto &ch:res) ch=-ch;
        }
        cout << res.size() << ln;
        for (auto ch:res) cout << ch << " ";
        cout << ln;
        // vector<ll> pref(res.size());
        // for (ll i=0; i<(ll)res.size(); i++){
        //     pref[i]=res[i];
        //     if (i) pref[i]+=pref[i-1];
        //     if (i+1>=mn){
        //         if ((pref[i]-(i-mn>=0?pref[i-mn]:0)>=0 and mn==n) or (pref[i]-(i-mn>=0?pref[i-mn]:0)<=0 and mn!=n)){
        //             cout << "Incorrect"; exit(0);
        //         }
        //     }else if (i+1>=mx){
        //         if ((pref[i]-(i-mx>=0?pref[i-mx]:0)>=0 and mx==n) or (pref[i]-(i-mx>=0?pref[i-mx]:0)<=0 and mx!=n)){
        //             cout << "Incorrect"; exit(0);
        //         }
        //     }
        // }
    }

}
/*
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
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24