Submission #65822

#	Time	Username	Problem	Language	Result	Execution time	Memory
65822		kingpig9	Nice sequence (IZhO18_sequence)	C++11	100 / 100	1671 ms	35400 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 4e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N, M;
stack<int> stk;
vector<int> topo;
int indeg[MAXN];

bool moo (int g, bool isfinal = false) {
	if (isfinal) {
		topo.clear();
	}
	//x -> x + M or x + N -> x

	for (int x = 0; x <= g; x++) {
		indeg[x] = 0;
		//adj[x].clear();
	}

	for (int x = 0; x + M <= g; x++) {
		//adj[x].push_back(x + M);
		indeg[x + M]++;
	}
	for (int x = 0; x + N <= g; x++) {
		//adj[x + N].push_back(x);
		indeg[x]++;
	}

	for (int x = 0; x <= g; x++) {
		if (indeg[x] == 0) {
			stk.push(x);
		}
	}

	while (!stk.empty()) {
		int x = stk.top();
		stk.pop();
		if (isfinal) {
			topo.push_back(x);
		}
		if (x - N >= 0 && --indeg[x - N] == 0) {
			stk.push(x - N);
		}
		if (x + M <= g && --indeg[x + M] == 0) {
			stk.push(x + M);
		}
	}

	for (int x = 0; x <= g; x++) {
		if (indeg[x]) {
			return false;
		}
	}
	return true;
}

int ans[MAXN];

int go() {
	int lo = min(N, M) - 1, hi = N + M;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (moo(mid)) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
	assert(moo(lo, true));

	int ind0 = find(all(topo), 0) - topo.begin();
	for (int i = 0; i <= lo; i++) {
		ans[topo[i]] = i - ind0;
	}
	for (int i = lo; i >= 1; i--) {
		ans[i] -= ans[i - 1];
	}
	return lo;
}

int main() {
	int nq;
	scanf("%d", &nq);
	for (int qi = 1; qi <= nq; qi++) {
		scanf("%d %d", &N, &M);
		int len = go();
		printf("%d\n", len);
		for (int i = 1; i <= len; i++) {
			printf("%d ", ans[i]);
		}
		puts("");
	}
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &nq);
  ~~~~~^~~~~~~~~~~
sequence.cpp:96: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