제출 #1130646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130646		Gray	Nice sequence (IZhO18_sequence)	C++20	0 / 100	0 ms	328 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){
    pref[i]=-1;
    ll mx=1;
    for (auto j:A[i]){
        if (pref[j]==-1) {pos=0;}
        else{
            if (!pref[j]) dfs(j);
            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;
    for (ll i=0; i<=len and pos; i++){
        if (!pref[i]) dfs(i);
    }
    if (pos==0) return 0;
    return 1;
}

void solve(){
    ll n, m; cin >> n >> m;
    ll l=0, r=n+m+n+m;
    while (l+1<r){
        ll mid = (l+r)/2;
        if (check(n, m, mid)) l=mid;
        else r=mid;
    }
    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: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24