제출 #1191126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191126		lopkus	Nice sequence (IZhO18_sequence)	C++20	100 / 100	732 ms	89972 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;

vector<ll> pref;
vector<vector<ll>> A;
bool pos;
void dfs(ll i, ll starter){
    pref[i]=-1;
    ll mx=starter;
    for (auto j:A[i]){
        if (pref[j]==-1) {pos=0;}
        else{
            if (!pref[j]) dfs(j, starter);
            mx=max(mx, pref[j]+1);
        }
    }
    pref[i]=mx;
}

bool check(ll n, ll m, ll len){
    pref.assign(len+1, 0);
    A.assign(len+1, vector<ll>());
    for (ll i=1; i<=len; i++){
        if (i>=n) A[i-n].push_back(i);
        if (i>=m) A[i].push_back(i-m);
    }
    pos=1; ll starter=1;
    for (ll i=0; i<=len and pos; i++){
        if (!pref[i]) dfs(i, starter++);
    }
    if (pos==0) return 0;
    return 1;
}

void solve(){
    ll n, m; cin >> n >> m;
    if (max(n, m)%min(n, m)==0){
        cout << max(n, m)-1 << ln;
        for (ll i=0; i<max(n, m)-1; i++){
            cout << (max(n, m)==n?1:-1) << " ";
        }
        cout << ln; return;
    }
    // m%n
    ll l = m+n-1-__gcd(m, n);
    check(n, m, l);
    cout << l << ln;
    for (ll i=1; i<=l; i++){
        cout << pref[i]-pref[i-1] << " ";
    }
    cout << ln;
}
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: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24