Submission #634020

#	Time	Username	Problem	Language	Result	Execution time	Memory
634020		Tob	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2068 ms	42756 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

ll nxt() {ll num; cin >> num; return num;}

const int maxn = 4e5 + 7;

int n, m;
bool ndag;
vector <int> v;
vector <int> adj[maxn];
int val[maxn], bio[maxn];

void dfs(int x) {
	bio[x] = 1;
	for (auto it : adj[x]) {
		if (bio[it] == 2) continue;
		if (bio[it] == 1) {
			ndag = 1;
			continue;
		}
		dfs(it);
	}
	bio[x] = 2;
	v.pb(x);
}

bool stask(int ma) {
	for (int i = 0; i <= ma; i++) adj[i].clear();
	v.clear();
	for (int i = 0; i <= ma; i++) bio[i] = 0;
	ndag = 0;
	
	for (int i = 0; i <= ma; i++) if (i + m <= ma) adj[i].pb(i+m);
	for (int i = 0; i <= ma; i++) if (i + n <= ma) adj[i+n].pb(i);
	
	for (int i = 0; i <= ma; i++) {
		if (!bio[i]) dfs(i);
	}
	
	if (ndag) return 1;
	
	int cc = 0;
	
	reverse(all(v));
	
	for (auto it : v) {
		val[it] = cc++;
	}
	
	vector <int> ps (ma+1, 0);
	
	for (int i = 1; i <= ma; i++) {
		ps[i] = ps[i-1] + val[i] - val[i-1];
	}
	
	for (int i = 1; i <= ma; i++) {
		if (i - m >= 0) {
			if (ps[i] - ps[i-m] <= 0) return 1;
		}
		if (i - n >= 0) {
			if (ps[i] - ps[i-n] >= 0) return 1;
		}
	}
	return 0;
}

void task() {
	cin >> n >> m;
	
	ll lo = max(n, m) - 1, hi = max(n, m) * 2;
	
	if (n == m) {
		cout << lo << "\n"; 
		for (int i = 1; i <= lo; i++) cout << "1 ";
		cout << "\n";
		return;
	}
	
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		if (stask(mid)) hi = mid - 1;
		else lo = mid;
	}
	
	stask(hi);
	
	cout << hi << "\n";
	
	for (int i = 1; i <= hi; i++) {
		cout << val[i] - val[i-1] << " ";
	}
	cout << "\n";
}

int main () {
	FIO;
	int t;
	
	cin >> t;
	
	while (t--) task();

	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: 0 / 24