Submission #378897

#	Time	Username	Problem	Language	Result	Execution time	Memory
378897		Kevin_Zhang_TW	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1571 ms	34240 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;

bool valid(int n, int m, int len, bool output = false) {

	vector<int> indeg(len + 1);
	for (int i = 1;i <= len;++i) {
		if (i >= n) {
			++indeg[i];
		}
		if (i >= m) {
			++indeg[i - m];
		}
	}
	vector<int> q;
	for (int i = 0;i <= len;++i) if (indeg[i] == 0)
		q.pb(i);

	if (q.empty()) return false;

	for (int i = 0;i < q.size();++i) {
		int x = q[i];

		if (x >= m) {
			if (--indeg[x - m] == 0)
				q.pb(x - m);
		}
		if (x + n <= len) {
			if (--indeg[x + n] == 0)
				q.pb(x + n);
		}
	}

	if (q.size() != len + 1) return false;

	if (output) {
		cout << len << '\n';
		vector<int> res(len + 1);

		int lst = len + 10;

		for (int i = 0;i <= len;++i) {
			int x = q[i];
			res[x] = --lst;
			if (x == 0) res[x] = 0;
			lst = res[x];
		}

		for (int i = 1;i <= len;++i)
			cout << res[i] - res[i-1] << " \n"[i==len];
	}
	return true;
};

void solve() {
	int n, m;
	cin >> n >> m;

	int U = 4;
	while (valid(n, m, U<<1)) U <<= 1;
	int res = 0;

	while (U) {
		if (valid(n, m, res | U))
			res |= U;
		U >>= 1;
	}
	valid(n, m, res, true);
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T--)
		solve();
}

Compilation message (stderr)

sequence.cpp: In function 'bool valid(int, int, int, bool)':
sequence.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0;i < q.size();++i) {
      |                 ~~^~~~~~~~~~
sequence.cpp:50:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |  if (q.size() != len + 1) return false;
      |      ~~~~~~~~~^~~~~~~~~~

• 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