oj.uz

Submission #496009

# Submission time Handle Problem Language Result Execution time Memory
496009 2021-12-20T11:37:23 Z armashka Nice sequence (IZhO18_sequence) C++17
34 / 100
 990 ms 262148 KB 
#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 4e5 + 5;
const ll M = 1e8;
const ll inf = 1e3;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            
 
int n, m, used[N], pr[N];
vector <int> g[N], order;
bool ok;
 
void dfs(int v) {
	used[v] = 1;
	for (auto to : g[v]) {
		if (used[to] == 1) {
			ok = 0;
        }
		if (!used[to]) dfs(to);
	}
	used[v] = 2;                                                        
}

bool check(int x) {
	ok = 1;
    for (int i = 0; i <= x; ++ i) {
        if (i >= n) g[i - n].pb(i);
        if (i >= m) g[i].pb(i - m);
    }
    for (int i = 0; i <= x; ++ i) used[i] = 0;
    for (int i = 0; i <= x; ++ i) {
		if (used[i] == 0) {
            dfs(i);
		}
    }
    for (int i = 0; i <= x; ++ i) g[i].clear();
	return ok;
}

void qfs(int v) {
    used[v] = 1;
	for (auto to : g[v]) qfs(to);
    order.pb(v);
}

const void solve(/*Armashka*/) {
	cin >> n >> m;
	int l = 1, r = n + m, len = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) l = mid + 1, len = mid;
		else r = mid - 1;		
    }
    for (int i = 0; i <= len; ++ i) {
        if (i >= n) g[i - n].pb(i);
        if (i >= m) g[i].pb(i - m);
    }
    for (int i = 0; i <= len; ++ i) used[i] = 0;
	for (int i = 0; i <= len; ++ i) {
	   if (!used[i]) qfs(i);
    }
    reverse(all(order));
	for (int i = 0; i <= len; ++ i) {
		pr[order[i]] = i;
    } 
	cout << len << "\n";
	for (int i = 1; i <= len; ++ i) {
		cout << -(pr[i] - pr[i - 1]) << " ";
	}
	cout << "\n";
	for (int i = 0; i <= len; ++ i) pr[i] = 0, g[i].clear();
	order.clear();
}
 
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
    cin >> tt;
    while (tt --) {
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9772 KB Ok
2 Correct 5 ms 9756 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9696 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 7 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 5 ms 9676 KB Ok
12 Correct 5 ms 9676 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 6 ms 9728 KB Ok
5 Correct 6 ms 9676 KB Ok
6 Correct 62 ms 18192 KB Ok
7 Correct 990 ms 142152 KB Ok
8 Correct 166 ms 43048 KB Ok
9 Runtime error 510 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 5 ms 9676 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 5 ms 9604 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9676 KB Ok
8 Correct 5 ms 9676 KB Ok
9 Correct 5 ms 9676 KB Ok
10 Correct 5 ms 9676 KB Ok
11 Correct 6 ms 9676 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 6 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 8 ms 9676 KB Ok
6 Runtime error 545 ms 262148 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9772 KB Ok
2 Correct 5 ms 9756 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9696 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 7 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 5 ms 9676 KB Ok
12 Correct 5 ms 9676 KB Ok
13 Correct 6 ms 9676 KB Ok
14 Correct 5 ms 9676 KB Ok
15 Correct 5 ms 9676 KB Ok
16 Correct 5 ms 9604 KB Ok
17 Correct 5 ms 9676 KB Ok
18 Correct 5 ms 9676 KB Ok
19 Correct 5 ms 9676 KB Ok
20 Correct 5 ms 9676 KB Ok
21 Correct 5 ms 9676 KB Ok
22 Correct 5 ms 9676 KB Ok
23 Correct 6 ms 9676 KB Ok
24 Correct 10 ms 9872 KB Ok
25 Correct 13 ms 10080 KB Ok
26 Correct 9 ms 9992 KB Ok
27 Correct 10 ms 10060 KB Ok
28 Correct 10 ms 9944 KB Ok
29 Correct 8 ms 9932 KB Ok
30 Correct 9 ms 9804 KB Ok
31 Correct 9 ms 9936 KB Ok
32 Correct 10 ms 9932 KB Ok
33 Correct 10 ms 10060 KB Ok
34 Correct 22 ms 10716 KB Ok
35 Correct 25 ms 11204 KB Ok
36 Correct 43 ms 18488 KB Ok
37 Correct 22 ms 10696 KB Ok
38 Correct 24 ms 10704 KB Ok
39 Correct 21 ms 10440 KB Ok
40 Correct 26 ms 11340 KB Ok
41 Correct 25 ms 11084 KB Ok
42 Correct 21 ms 10748 KB Ok
43 Correct 24 ms 11204 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9772 KB Ok
2 Correct 5 ms 9756 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9696 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 7 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 5 ms 9676 KB Ok
12 Correct 5 ms 9676 KB Ok
13 Correct 5 ms 9676 KB Ok
14 Correct 6 ms 9676 KB Ok
15 Correct 5 ms 9676 KB Ok
16 Correct 6 ms 9728 KB Ok
17 Correct 6 ms 9676 KB Ok
18 Correct 62 ms 18192 KB Ok
19 Correct 990 ms 142152 KB Ok
20 Correct 166 ms 43048 KB Ok
21 Runtime error 510 ms 262148 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9772 KB Ok
2 Correct 5 ms 9756 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 5 ms 9676 KB Ok
6 Correct 5 ms 9676 KB Ok
7 Correct 5 ms 9696 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 7 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 5 ms 9676 KB Ok
12 Correct 5 ms 9676 KB Ok
13 Correct 5 ms 9676 KB Ok
14 Correct 6 ms 9676 KB Ok
15 Correct 5 ms 9676 KB Ok
16 Correct 6 ms 9728 KB Ok
17 Correct 6 ms 9676 KB Ok
18 Correct 62 ms 18192 KB Ok
19 Correct 990 ms 142152 KB Ok
20 Correct 166 ms 43048 KB Ok
21 Runtime error 510 ms 262148 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -