제출 #496063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496063		vinnipuh01	Nice sequence (IZhO18_sequence)	C++17	0 / 100	84 ms	44988 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[ 200001 ], used[ 200001 ];
vector <int> v[ 200001 ], ts, vv;

void dfs( int u ) {
	used[ u ] = 1;
	for ( auto to : v[ u ] ) {
		if ( !used[ to ] )
			dfs( to );
		else if ( used[ to ] == 1 ) {
			ans = 1;
			return;
		}
	}
	ts.push_back( u );
	used[ u ] = 2;
}

bool ok( int x ) {
	for ( int i = 1; i <= x; i ++ ) {
		used[ i ] = 0;
		p[ i ] = 0;
		v[ i ].clear();
	}
	used[ 0 ] = 0;
	v[ 0 ].clear();
	for ( int i = n; i <= x; i ++ ) {
		v[ i - n ].push_back( i );
	}
	for ( int i = m; i <= x; i ++ ) {
		v[ i ].push_back( i - m );
	}
	ts.clear();
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
	if ( ans )
		return false;
	num = 0;
//	cout << x << " - ";
	for ( auto i : ts )
		p[ i ] = ++num;
//	for ( int i = 0; i <= x; i ++ )
//		cout << p[ i ] << " ";
//	cout << "\n";
	for ( int i = 1; i <= x; i ++ ) {
		p[ i ] -= p[ 0 ];
	}
	p[ 0 ] = 0;
	vv.clear();
	for ( int i = 1; i <= x; i ++ ) {
		vv.push_back( p[ i ] - p[ i - 1 ] );
	}
	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;
		while ( r - l > 1 ) {
			mid = ( r + l ) / 2;
			if ( ok( mid ) )
				l = mid;
			else
				r = mid - 1;
		}
		if ( ok( r ) ) {
			cout << r << "\n";
			for ( auto i : vv )
				cout << i << " ";
		}
		else {
			cout << l << "\n";
			for ( auto i : vv )
				cout << i << " ";
		}
		cout << "\n";
	}
}

• 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