oj.uz

Submission #496062

# Submission time Handle Problem Language Result Execution time Memory
496062 2021-12-20T13:50:30 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
15 / 100
 902 ms 28344 KB 
#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 = 200000;
		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.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 14152 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 11912 KB Jury has the better answer : jans = 3, pans = -2
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 13972 KB Jury has the better answer : jans = 3, pans = -3
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11848 KB Ok
2 Correct 72 ms 10080 KB Ok
3 Correct 65 ms 9928 KB Ok
4 Correct 77 ms 9800 KB Ok
5 Correct 70 ms 9672 KB Ok
6 Correct 484 ms 23464 KB Ok
7 Correct 466 ms 25720 KB Ok
8 Correct 902 ms 28344 KB Ok
9 Correct 610 ms 25524 KB Ok
10 Correct 352 ms 17180 KB Ok
11 Correct 608 ms 27064 KB Ok

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 14152 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 14152 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 14152 KB there is incorrect sequence
2 Halted 0 ms 0 KB -