oj.uz

Submission #634981

# Submission time Handle Problem Language Result Execution time Memory
634981 2022-08-25T09:51:50 Z drkarlicio2107 Nice sequence (IZhO18_sequence) C++14
38 / 100
 1000 ms 40828 KB 
#include <bits/stdc++.h>
using namespace std;
int vis [400010];  long long int  c=0; long long int n, m;
vector < int > g [400010];
vector < long long int > ans;
long long int  o [400010];
int vis2 [400010];
int vis3 [400010];
void dfs ( int  x,  long long int  d){
	if (vis [x]) return ;
	vis [x]=1;
	if (x+n<=d){
		g [x+n].push_back (x); //dfs (x+n, d); 
	}
	if (x+m<=d){
		g [x].push_back (x+m); dfs (x+m, d);
	}
	return ;
}
void dfs2 ( int  v) {
    vis2[v]=1;
    for ( long long int  u : g[v]) {
        if (!vis2[u]) dfs2(u);
    }
    ans.push_back(v);
    return ;
}

void is_cycle ( long long int  x) {
	if (vis3 [x]==1){
		c=1; return ;
	}
	if (vis3 [x]) return ;
	vis3 [x]=1;
	for ( long long int  u : g[x]) is_cycle (u);
	vis3 [x]=2;
	return ;
}

void sort_top( long long int  d) {
    memset (vis2, 0, sizeof vis2); ans.clear();
    for ( long long int  i=0; i<=d; i++) {
        if (!vis2[i])
            dfs2(i);
    }
    reverse(ans.begin(), ans.end());
    return ;
}
 long long int  ok ( long long int  d){
	memset (vis, 0, sizeof vis);  
	memset (vis3, 0, sizeof vis3); 
	c=0;
	for ( long long int  i=0; i<200010; i++) g [i].clear();
	for ( long long int  i=0; i<=d; i++){
		if (!vis [i]) dfs (i, d);
	}
	for ( long long int  i=1; i<=d; i++) is_cycle (i);
	if (c) return 0;
	sort_top (d);
	return 1;
}
int  main(){
	 long long int  t; cin >> t;
	while (t--){
		ans.clear ();
		cin >> n >> m;
		long long int  lo=0, hi=2*max(n, m);
		while (lo!=hi){
			 long long int  mid=(lo+hi+1)/2;
			if (ok (mid)) lo=mid;
			else hi=mid-1;
		}
		cout << lo << endl; //cout << ans.size();
		 long long int  pr=0;
		for ( long long int  i=0; i<=lo; i++){
			if (ans [lo]==0) break;
			pr--;
		}
		for ( long long int  i=0; i<=lo; i++){
			//cout << ans [i] << " ";
			o [ans [i]]=pr; pr++;
		}
		for ( long long int  i=1; i<lo+1; i++){
			//cout << o [i] << "x";
			cout << o [i]-o [i-1] << " ";
		}
		cout << endl;
	}
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 25772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14292 KB Ok
2 Correct 41 ms 14368 KB Ok
3 Correct 43 ms 14388 KB Ok
4 Correct 52 ms 14292 KB Ok
5 Correct 48 ms 14292 KB Ok
6 Correct 86 ms 14636 KB Ok
7 Correct 135 ms 15724 KB Ok
8 Correct 90 ms 15052 KB Ok
9 Correct 132 ms 16076 KB Ok
10 Correct 113 ms 15236 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14292 KB Ok
2 Correct 29 ms 14292 KB Ok
3 Correct 34 ms 14292 KB Ok
4 Correct 30 ms 14292 KB Ok
5 Correct 29 ms 14292 KB Ok
6 Correct 31 ms 14292 KB Ok
7 Correct 32 ms 14292 KB Ok
8 Correct 31 ms 14292 KB Ok
9 Correct 39 ms 14292 KB Ok
10 Correct 35 ms 14368 KB Ok
11 Correct 35 ms 14292 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14292 KB Ok
2 Correct 35 ms 14396 KB Ok
3 Correct 37 ms 14348 KB Ok
4 Correct 43 ms 14292 KB Ok
5 Correct 47 ms 14292 KB Ok
6 Correct 744 ms 35196 KB Ok
7 Correct 516 ms 35044 KB Ok
8 Correct 1000 ms 38436 KB Ok
9 Correct 769 ms 35896 KB Ok
10 Correct 502 ms 28420 KB Ok
11 Correct 928 ms 40828 KB Ok

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 25772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 25772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 25772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -