Submission #335337

#TimeUsernameProblemLanguageResultExecution timeMemory
335337limabeansNice sequence (IZhO18_sequence)C++17
100 / 100
1954 ms45676 KiB
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;





int n, m;

bool viz[maxn];
int p[maxn]; //p[i-m] < p[i] > p[i+n]
vector<int> topo;



void dfs(int i, int len) {
    assert(!viz[i]);
    viz[i]=true;
    if (i-m>=0 && !viz[i-m]) dfs(i-m,len);
    if (i+n<=len && !viz[i+n]) dfs(i+n,len);
    topo.push_back(i);
}

bool test(int len) {

    topo.clear();
    for (int i=0; i<=len; i++) {
	viz[i]=false;
	p[i]=0;
    }

    for (int i=0; i<=len; i++) {
	if (!viz[i]) dfs(i,len);
    }
    for (int i=0; i<=len; i++) {
	p[topo[i]]=i;
    }

    for (int i=0; i<=len; i++) {
	if (i-n>=0 && p[i]>=p[i-n]) return false;
	if (i+m<=len && p[i+m]<=p[i]) return false;
    }
    return true;
}

void solve() {
    cin>>n>>m;
    int lo=0;
    int hi=4e5+1;
    while (hi-lo>1) {
	int mid=(lo+hi)/2;
	if (test(mid)) {
	    lo=mid;
	} else {
	    hi=mid;
	}
    }

    test(lo);
    cout<<lo<<"\n";
    if (lo) {
	for (int i=1; i<=lo; i++) {
	    cout<<p[i]-p[i-1]<<" ";
	}
	cout<<"\n";
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    int t;
    cin>>t;
    while (t--) {
	solve();
    }	    
    
    
    return 0;
}
#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...