oj.uz

Submission #633596

# Submission time Handle Problem Language Result Execution time Memory
633596 2022-08-22T19:27:49 Z lovrot Gift (IZhO18_nicegift) C++11
0 / 100
 2000 ms 26780 KB 
#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], lastans;
bool bio[N], vis[N], cyc[N];

vector<int> g[N];
stack<int> stk;

void pocisti(){ 
	memset(bio, 0, sizeof(bio));
	memset(vis, 0, sizeof(vis));
	memset(cyc, 0, sizeof(cyc));
	for(int i = 0; i < N; i++){ 
	 	g[i].clear();
	}
}

bool cycp(int u){ 	
	bio[u] = true;
	cyc[u] = true;
	for(int v : g[u]){ 
		// cout << u << " -> " << v << " " << bio[v] << "\n"; 
		if(bio[v]){ 
			return true;
		}
		if(cycp(v)){ 
			return true;	
		}
	}
	bio[u] = false;
	return false;
}

bool probaj(int x){ 
	pocisti();

	for(int i = 1; i <= x; i++){ 
		if(i - m >= 0){
			g[i].pb(i - m);
			// cout << i << " " << i - m << " +\n";
		}
		if(i - n >= 0){
			g[i - n].pb(i);
			// cout << i - n << " " << i << " +\n";
		}
	}
	
	for(int i = 0; i <= x; i++){ 
		if(!cyc[i]){
			if(cycp(i))
				return false;
		}
	}
	return true;
}

void topSort(int u){ 
	vis[u] = true;
	for(int v : g[u]){ 
		if(vis[v]) continue;
		topSort(v);
	}
	stk.push(u);
}

void output(int ans){ 
	if(ans < min(n, m)){
		cout << ans << "\n"; 
		lastans = ans;
		for(int i = 0; i < ans; i++){ 
			cout << "-1 ";
		}
		cout << "\n";
		return;
	}

	for(int i = 0; i <= ans; i++)
		if(!vis[i]) topSort(i);

	int cnt = ans + 3;
	while(!stk.empty()){ 
		p[stk.top()] = cnt--;
		// cout << stk.top() << " " << p[stk.top()] << " ;\n";
		stk.pop(); 
	}

	cout << ans << "\n";
	lastans = ans;

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

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

	int lo = 0, hi = n + m + 1;
	while(hi - lo > 1){ 
		int mi = (lo + hi) / 2;
	//	cout << mi << ": \n";
		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();
	//	cout << "-----\n";
	}
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 26708 KB Added number should be positive
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 26708 KB Added number should be positive
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 26708 KB Added number should be positive
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 26780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 26708 KB Added number should be positive
2 Halted 0 ms 0 KB -