Submission #335337

#	Time	Username	Problem	Language	Result	Execution time	Memory
335337		limabeans	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1954 ms	45676 KiB

sequence

#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;
}

• 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