제출 #496138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496138		vinnipuh01	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2068 ms	55356 KiB

sequence

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
 
using namespace std;
 
const long long oo = 1000000000000000000;
 
long long int  sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
 
 
/*
    ViHHiPuh
 
   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))
 
 
    cout << fixed << setprecision(6) << x;
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    freopen ( "sum.in", "r", stdin )
*/
 
int n, m, p[ 400001 ], used[ 400001 ], nn[ 400001 ], mm[ 400001 ];
vector <int> v[ 400001 ], ts, vv;
 
void dfs( int u ) {
	used[ u ] = 1;
	for ( int i = 1; i <= 2; i ++ ) {
		int to;
		if ( ans )
			return;
		if ( i == 1 ) {
			if ( nn[ u ] >= 0 )
				to = nn[ u ];
			else
				continue;
		}
		else {
			if ( mm[ u ] >= 0 )
				to = mm[ u ];
			else
				continue;
		}
		if ( !used[ to ] )
			dfs( to );
		else if ( used[ to ] == 1 ) {
			ans = 1;
			return;
		}
	}
		if ( ans )
			return;
	used[ u ] = 2;
}
 
void dfs1( int u ) {
	used[ u ] = 1;
	for ( int i = 1; i <= 2; i ++ ) {
		int to;
		if ( i == 1 ) {
			if ( nn[ u ] >= 0 )
				to = nn[ u ];
			else
				continue;
		}
		else {
			if ( mm[ u ] >= 0 )
				to = mm[ u ];
			else
				continue;
		}
		if ( !used[ to ] )
			dfs1( to );
	}
	ts.push_back( u );
}
 
bool ok( int x ) {
	for ( int i = 0; i <= x; i ++ ) {
		used[ i ] = 0;
		nn[ i ] = -1;
		mm[ i ] = -1; 
		if ( i >= n )
			nn[ i - n ] = i;
		if ( i >= m )
			mm[ i ] = i - m; 
	}
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
	if ( ans )
		return false;
	if ( sum ) {
		ts.clear();
		for ( int i = 0; i <= x; i ++ ) {
			p[ i ] = 0;
			used[ i ] = 0;
		}
		for ( int i = 0; i<= x; i ++ ) {
			if ( !used[ i ] )
				dfs1( i );
		}
		num = 0;
		for ( auto i : ts )
			p[ i ] = ++num;
		for ( int i = 1; i <= x; i ++ ) {
			p[ i ] -= p[ 0 ];
		}
		p[ 0 ] = 0;
	}
	return true;
}
 
int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	int l, r, mid;
	while ( t -- ) {
		cin >> n >> m;
		mx = max( n, m );
		l = mx - 1;
		r = 400000;
		sum = 0;
		while ( r - l > 1 ) {
			mid = ( r + l ) / 2;
			if ( ok( mid ) )
				l = mid;
			else
				r = mid - 1;
		}
		if ( ok( r ) ) {
			sum = 1;
			ok( r );
			cout << r << "\n";
			for ( int i = 1; i <= r; i ++ )
				cout << p[ i ] - p[ i - 1 ] << " ";
		}
		else {
			sum = 1;
			ok( l );
			cout << l << "\n";
			for ( int i = 1; i <= l; i ++ )
				cout << p[ i ] - p[ i - 1 ] << " ";
		}
		cout << "\n";
	}
}

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