Submission #382797

#	Time	Username	Problem	Language	Result	Execution time	Memory
382797		maximath_1	Nice sequence (IZhO18_sequence)	C++11	100 / 100	545 ms	34500 KiB

sequence

// binary search the length
// construct a graph of len + 1 vertices
// draw a directed edge from u to v if we require pref[u] - pref[v] < 0
// start indexing pref[x] from source to sink
// as you can see if we traverse the graph in that manner
// the pref[x]s will be numbered in a way s.t. all requirements are fulfilled
// get final array from pref
// complexity O(T * (N + M)log(N + M)), very tight to TL

// now we will prove that the final length is N + M - gcd(N, M) - 1
// first of all, we can show that if len = N + M - gcd(N, M),
// there is a cycle in the set of vertices divisible by gcd(N, M)
// if we remove vertex N + M - gcd(N, M), the cycle will break as (N + M - gcd(N, M)) is divisible by gcd(N, M)
// thus N + M - gcd(N, M) - 1 is max
// complexity O(T * (N + M))
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;

#define ll long long
#define ld long double
const int MX = 200005;
const int LG = (int)log2(MX) + 2;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;

#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}

int tc, n, m;

pair<bool, vector<int> > check(int len){
	vector<int> deg(len + 1, 0);

	for(int i = 0; i <= len; i ++){
		if(i - n >= 0) deg[i - n] ++;
		if(i + m <= len) deg[i + m] ++;
	}

	vector<int> pref(len + 1, 0);
	queue<int> q;
	for(int i = 0; i <= len; i ++){
		if(deg[i] == 0)
			q.push(i);
	}

	int cnt = 0;
	for(; q.size();){
		int nw = q.front(); q.pop();
		pref[nw] = ++ cnt;

		if(nw - n >= 0){
			deg[nw - n] --;
			if(deg[nw - n] == 0)
				q.push(nw - n);
		}

		if(nw + m <= len){
			deg[nw + m] --;
			if(deg[nw + m] == 0)
				q.push(nw + m);
		}
	}

	bool valid = 1;
	for(int i = 0; i <= len; i ++)
		if(deg[i] > 0) valid = 0;

	vector<int> res(len, 0);
	for(int i = 0; i < len; i ++)
		res[i] = pref[i + 1] - pref[i];

	return make_pair(valid, res);
}

int main(){
	cin(tc);

	for(; tc --;){
		cin(n); cin(m);

		int rs = n + m - __gcd(n, m) - 1;
		vector<int> ans = check(rs).second;

		printf("%d\n", rs);
		for(int i = 0; i < rs; i ++)
			printf("%d ", ans[i]);
		printf("\n");
	}
	
	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