Submission #46528

#	Time	Username	Problem	Language	Result	Execution time	Memory
46528		Bruteforceman	Nice sequence (IZhO18_sequence)	C++11	100 / 100	1751 ms	56168 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
int N, M;
vector <int> g[400010];
int solution[400010], pref[400010];
int deg[400010];
int v[400010];
void solve(int size) {
	for(int i = 0; i <= size; i++) {
		g[i].clear();
		deg[i] = 0;
	}
	for(int i = N; i <= size; i++) {
		g[i].push_back(i - N);
		++deg[i - N];
	}
	for(int i = 0; i <= size - M; i++) {
		g[i].push_back(i + M);
		++deg[i + M];
	}
	queue <int> Q;
	for(int i = 0; i <= size; i++) {
		if(deg[i] == 0) {
			Q.push(i);
		}
	}
	int cnt = 0;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		v[cnt++] = x;
		for(auto i : g[x]) {
			--deg[i];
			if(deg[i] == 0) {
				Q.push(i);
			}
		}
	}
	if(cnt == size + 1) {
		for(int i = 0; i < cnt; i++) {
			if(v[i] == 0) {
				int cur = 0;
				for(int j = i-1; j >= 0; j--) {
					pref[v[j]] = --cur; 
				}
				cur = 0;
				for(int j = i+1; j < cnt; j++) {
					pref[v[j]] = ++cur;
				}
				pref[v[i]] = 0;
				break;
			}
		}
		for(int i = 1; i <= size; i++) {
			solution[i] = pref[i] - pref[i - 1];
		}
	} else {
		assert(false);
	}
}

int main(int argc, char const *argv[])
{
	int test;
	scanf("%d", &test);
	for(int cs = 1; cs <= test; cs++) {
		scanf("%d %d", &N, &M);		
		int ans = 0;
		if(N == M) {
			ans = N-1;
		} else if (N > M) {
			int diff = N % M;
			for(int i = 0; i < M; i++) {
				long long val = 1LL * i * diff;
				val %= M;
				ans = max(ans, (int) val);
			}
			ans += N - 1;
		} else {
			int diff = M % N;
			for(int i = 0; i < N; i++) {
				long long val = 1LL * i * diff;
				val %= N;
				ans = max(ans, (int) val);			}
			ans += M - 1;
		}
		solve(ans);
		printf("%d\n", ans);
		for(int i = 1; i <= ans; i++) {
			printf("%d ", solution[i]);
		}
		printf("\n");
	}
	return 0; 
}

Compilation message (stderr)

sequence.cpp: In function 'int main(int, const char**)':
sequence.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &test);
  ~~~~~^~~~~~~~~~~~~
sequence.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);  
   ~~~~~^~~~~~~~~~~~~~~~~

• 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