oj.uz

답안 #634918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634918 2022-08-25T08:43:22 Z drkarlicio2107 Nice sequence (IZhO18_sequence) C++14
0 / 100
 18 ms 7360 KB 
#include <bits/stdc++.h>
using namespace std;
int vis [200010]; int c=0; long long int n, m;
vector <int> g [200010];
vector <int> ans;
int o [200010];
int vis2 [200010];
int vis3 [200010];
void dfs (int x, int d){
	if (vis [x]) return ;
	vis [x]=1;
	if (x+n<=d){
		g [x].push_back (x+n); dfs (x+n, d); 
	}
	if (x+m<=d){
		g [x+m].push_back (x); //dfs (x+m, d);
	}
	return ;
}
void dfs2 (int v) {
    vis2[v]=1;
    for (int u : g[v]) {
        if (!vis2[u]) dfs2(u);
    }
    ans.push_back(v);
}

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

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

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 7360 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 7272 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 7252 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 7252 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 7360 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 7360 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 7360 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -