Submission #633880

#	Time	Username	Problem	Language	Result	Execution time	Memory
633880		lovrot	Nice sequence (IZhO18_sequence)	C++11	34 / 100	2092 ms	2000 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 = 2 * 1e5 + 10;

int n, m, p[N], g[N][2], ans;
int stk[N], pos;
int cyc[N], bio[N], ts[N], cookie;

int stackTop(){ 
	return stk[pos];
}

void stackPop(){ 
	pos--;
}

void stackPush(int x){ 
	pos++;
	stk[pos] = x;
	p[x] = pos;
}

bool cycp(int u){
	bio[u] = cookie;
	cyc[u] = cookie;
	// cout << u << "\n";
	int lv = u - m, uv = u + n;
	if(lv >= 0){
		if(cyc[lv] == cookie) 
			return true;
		if(cycp(lv))
			return true;	
	}
	if(uv <= ans){
		if(cyc[uv] == cookie) 
			return true;
		if(cycp(uv))
			return true;	
	}
	cyc[u] = -cookie;
	return false;
}

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

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++;

	// for(int i = 0; i <= ans; i++){ 
	// 	g[i][0] = g[i][1] = -1; 
	// 	if(i - m >= 0) g[i][0] = i - m;
	// 	if(i - n >= 0) g[i - n][1] = i;
	// }
	// for(int i = 0; i <= x; i++) cout << i << ": " << g[i][0] << " " << g[i][1] << "\n";

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

void task(){ 
	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();
}

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

	while(t--){ 
		task();
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void task()':
sequence.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 9
• Subtask 3: 14 / 14
• Subtask 4: 0 / 15
• Subtask 5: 14 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24