Submission #46507

#	Time	Username	Problem	Language	Result	Execution time	Memory
46507		Bruteforceman	Nice sequence (IZhO18_sequence)	C++11	76 / 100	2074 ms	34120 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
int N, M;
vector <int> g[400010];
vector <int> solution;
int deg[400010];

bool good(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);
		}
	}
	vector <int> v;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		v.push_back(x);
		for(auto i : g[x]) {
			--deg[i];
			if(deg[i] == 0) {
				Q.push(i);
			}
		}
	}
	if(v.size() == size + 1) {
		vector <int> pref (size + 1);
		solution.resize(size + 1);
		for(int i = 0; i < v.size(); 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 < v.size(); j++) {
					pref[v[j]] = ++cur;
				}
				break;
			}
		}
		for(int i = 1; i <= size; i++) {
			solution[i] = pref[i] - pref[i - 1];
		}
		return true;
	}
	return false;
}

int search(int b, int e) {
	if(b == e) {
		return b;
	}
	int m = (b + e + 1) >> 1;
	if(good(m)) return search(m, e);
	else return search(b, m - 1);
}

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 = search(0, N + M - 1);
		good(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 'bool good(int)':
sequence.cpp:39:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(v.size() == size + 1) {
     ~~~~~~~~~^~~~~~~~~~~
sequence.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
sequence.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = i+1; j < v.size(); j++) {
                      ~~^~~~~~~~~~
sequence.cpp: In function 'int main(int, const char**)':
sequence.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &test);
  ~~~~~^~~~~~~~~~~~~
sequence.cpp:77: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: 0 / 24