Submission #633775

#	Time	Username	Problem	Language	Result	Execution time	Memory
633775		lovrot	Nice sequence (IZhO18_sequence)	C++11	0 / 100	117 ms	262144 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 = 1e6;

int n, m, p[N], lastx, g[N][2], memo[N], cnt;
int stk[N], pos;

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

void stackPop(){ 
	pos--;
}

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

void pocisti(){ 
	pos = -1;
	for(int i = 0; i <= lastx; i++){ 
	 	g[i][0] = -1;
	 	g[i][2] = -1;
	 	memo[i] = 0; 
	}
}

bool cycp(int u){
	cnt++; 	
	memo[u] = cnt;
	if(g[u][0] != -1){
		if(memo[g[u][0]] < memo[u]){ 
			return true;
		}
		if(cycp(g[u][0])){ 
			return true;	
		}
	}
	if(g[u][1] != -1){
		if(memo[g[u][1]] < memo[u]){ 
			return true;
		}
		if(cycp(g[u][1])){ 
			return true;	
		}
	}
	return false;
}

void topSort(int u){ 
	memo[u] = N;
	if(g[u][0] != -1 && memo[g[u][0]] != -1){ 
		topSort(g[u][0]);
	}
	if(g[u][1] != -1 && memo[g[u][1]] != -1){ 
		topSort(g[u][1]);
	}
	stackPush(u);
}

void output(int ans){ 
	for(int i = 0; i <= ans; i++)
		if(memo[i] != -1) topSort(i);

	int val = ans;
	while(pos > -1){ 
		p[stackTop()] = val--;
		stackPop(); 
	}


	for(int i = ans; i >= 0; i--){
		p[i] -= p[0];
	}
	for(int i = 0; i <= ans; i++){ 
		if(i >= n && p[i] - p[i - n] >= 0){ 
			cout << -1 << "\n";
			return;
		}
		if(i >= m && p[i] - p[i - m] <= 0){ 
			cout << -1 << "\n";
			return;
		}	
		if(i > 0 && p[i] - p[i - 1] == 0){ 
			cout << -1 << "\n";
		}
	}
	cout << ans << "\n";
	for(int i = 1; i <= ans; i++) 
		cout << p[i] - p[i - 1] << " \n"[i == ans]; 
}

bool probaj(int x){ 
	pocisti();
	lastx = x;
	cnt = 0;

	for(int i = 1; i <= x; i++){ 
		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++){ 
		if(memo[i] == 0){
			if(cycp(i))
				return false;
		}
	}
	return true;
}

void task(){ 
	cin >> n >> m;

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;	
	cin >> t;

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

Compilation message (stderr)

sequence.cpp: In function 'void pocisti()':
sequence.cpp:32:10: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   32 |    g[i][2] = -1;
      |    ~~~~~~^
sequence.cpp: In function 'bool probaj(int)':
sequence.cpp:32:10: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   32 |    g[i][2] = -1;
      |    ~~~~~~^

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