Submission #385612

#	Time	Username	Problem	Language	Result	Execution time	Memory
385612		patrikpavic2	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1749 ms	48108 KiB

sequence

#include <cstdio>
#include <cstring>

#define PB push_back

using namespace std;

const int N = 4e5 + 500;

int bio[N], L[N], R[N];

void clean(){
	memset(bio, 0, sizeof(bio));
	memset(L, -1, sizeof(L));
	memset(R, -1, sizeof(R));
}

bool ima_ciklus(int x){
	bio[x] = 1;
	if(L[x] != -1 && bio[L[x]] == 1) return 1;
	if(R[x] != -1 && bio[R[x]] == 1) return 1;
	if(L[x] != -1 && bio[L[x]] != 2 && ima_ciklus(L[x])) return 1;
	if(R[x] != -1 && bio[R[x]] != 2 && ima_ciklus(R[x])) return 1;
	bio[x] = 2;
	return 0;
}

int P[N], cur = 0;

void topsort(int x){
	if(bio[x]) return;
	bio[x] = 1;
	if(L[x] != -1) topsort(L[x]);
	if(R[x] != -1) topsort(R[x]);
	P[x] = cur++;
}

bool check(int n, int a, int b, bool napravi = false){
	clean();
	for(int i = 0;i <= n;i++){
		if(i + a <= n) L[i + a] = i;
		if(i + b <= n) R[i] = i + b;
	}
	if(!napravi){
		for(int i = 0;i <= n;i++)
			if(!bio[i] && ima_ciklus(i)){
				return false;
			}
		return true;
	}
	cur = 0;
	for(int i = 0;i <= n;i++)
		topsort(i);
	for(int i = 1;i <= n;i++)
		P[i] -= P[0];
	P[0] = 0;
	printf("%d\n", n);
	for(int i = 1;i <= n;i++)
		printf("%d ", P[i] - P[i - 1]);
	printf("\n");
	return true;
	
}

int main(){
	int T; scanf("%d", &T);
	for(;T--;){
		int a, b; scanf("%d%d", &b, &a);
		int ans = 0;
		for(int i = 18;i >= 0;i--){
			if(ans + (1 << i) <= a + b && check(ans + (1 << i), a, b))
				ans += (1 << i);
		}
		check(ans, a, b, 1);
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  int T; scanf("%d", &T);
      |         ~~~~~^~~~~~~~~~
sequence.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   int a, b; scanf("%d%d", &b, &a);
      |             ~~~~~^~~~~~~~~~~~~~~~

• 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