Submission #633909

#	Time	Username	Problem	Language	Result	Execution time	Memory
633909		lovrot	Nice sequence (IZhO18_sequence)	C++11	100 / 100	1110 ms	46412 KiB

sequence

#include <bits/stdc++.h> 

#define pb push_back 
#define X first
#define Y second
#define pii pair<int, int>

using namespace std;

const int N = 4 * 1e5 + 10;

int t, n, m, p[N], ans, pos;
int bio[N], ts[N], cookie;

bool cycp(int u){
	if(bio[u] == cookie + 1 || bio[u] == cookie) return bio[u] == cookie;
	bio[u] = cookie;
	if(u - m >= 0 && cycp(u - m)) return true;
	if(u + n <= ans && cycp(u + n)) return true;
	bio[u] = cookie + 1;
	return false;
}

void topSort(int u){ 
	ts[u] = cookie;
	if(u - m >= 0){
		if(ts[u - m] != cookie) topSort(u - m);
	}
	if(u + n <= ans){ 
		if(ts[u + n] != cookie) topSort(u + n);
	}
	p[u] = ++pos;
}

void output(){ 
	for(int i = 0; i <= ans; i++)
		if(ts[i] != cookie) topSort(i);

	printf("%d\n", ans);
	for(int i = 1; i <= ans; i++) 
		printf("%d ", (p[i] - p[0]) - (p[i - 1] - p[0]));
	printf("\n");
}

bool probaj(){ 
	pos = -1;
	cookie += 2;

	for(int i = 0; i <= ans; i++){ 
		if(bio[i] != cookie + 1 && cycp(i)) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	
	scanf("%d", &t);

	while(t--){ 
		scanf("%d %d", &n, &m);

		int lo = 0, hi = (n + m) + 1;
		while(hi - lo > 1){ 
			int mi = (lo + hi) / 2;
			ans = mi;
			if(probaj())
				lo = mi;
			else 
				hi = mi;
		}
		ans = lo;
		probaj();
		output();
	}
	return 0;
}

Compilation message (stderr)

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