Submission #65821

#	Time	Username	Problem	Language	Result	Execution time	Memory
65821		kingpig9	Nice sequence (IZhO18_sequence)	C++11	58 / 100	2075 ms	24876 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;
vector<int> adj[MAXN];
vector<int> topo;
int indeg[MAXN];

bool moo (int g) {
	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]++;
	}

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

	while (!stk.empty()) {
		int x = stk.top();
		stk.pop();
		topo.push_back(x);
		for (int y : adj[x]) {
			if (--indeg[y] == 0) {
				stk.push(y);
			}
		}
	}

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

vector<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;
		}
	}
	moo(lo);

	vector<int> ans(lo + 1);
	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];
	}
	ans.erase(ans.begin());
	return ans;
}

int main() {
	int nq;
	scanf("%d", &nq);
	for (int qi = 1; qi <= nq; qi++) {
		scanf("%d %d", &N, &M);
		vector<int> ans = go();
		printf("%lu\n", ans.size());
		for (int x : ans) {
			printf("%d ", x);
		}
		puts("");
	}
}

Compilation message (stderr)

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