oj.uz

Submission #497793

# Submission time Handle Problem Language Result Execution time Memory
497793 2021-12-23T20:12:39 Z Ziel Nice sequence (IZhO18_sequence) C++17
76 / 100
 957 ms 48780 KB 
/**
 * LES GREATEABLES BRO TEAM
**/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = true;
void setIO(const string &f = "");

#define int ll
const int N = 3e5 + 156;
int was[N], visited[N];
vector<int> g[N], order;

bool dfs(int v) {
	was[v] = 1;
	for (int to: g[v]) {
		if (!was[to]) {
			if (dfs(to))
				return true;
		} else if (was[to] == 1)
			return true;
	}
	was[v] = 2;
	return false;
}
void dfs2(int v) {
	visited[v] = 1;
	for (int to: g[v]) {
		if (!visited[to])
			dfs2(to);
	}
	order.push_back(v);
}

void solve() {
    int n, m;
    cin >> n >> m;

    int lo = 0, hi = n + m, res = -1;
    while (lo <= hi) {
    	int mid = (lo + hi) / 2;

		for (int i = n; i <= mid; i++)
			g[i].push_back(i - n);
		for (int i = m; i <= mid; i++)
			g[i - m].push_back(i);

		bool have_cycle = false;
		for (int i = 0; i <= mid; i++) {
			if (!was[i] && dfs(i)) {
				have_cycle = true;
				break;
			}
		}
		for (int i = 0; i <= mid; i++) {
			was[i] = 0;
			if (sz(g[i])) g[i].clear();
		}

		if (have_cycle) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
			res = mid;
		}
    }


    cout << res << '\n';
    
    for (int i = n; i <= res; i++)
		g[i].push_back(i - n);
	for (int i = m; i <= res; i++)
		g[i - m].push_back(i);
    for (int i = 0; i <= res; i++) {
    	if (!visited[i])
    		dfs2(i);
    }
    reverse(order.begin(), order.end());
    vector<int> p(sz(order));
    for (int i = 0; i < sz(order); i++) {
    	p[order[i]] = i;
   	}
   	int x = p[0];
   	for (int i = 0; i < sz(p); i++)
   		p[i] -= x;
   	for (int i = 1; i < sz(p); i++)
   		cout << p[i] - p[i - 1] << ' ';

   	order.clear();
   	for (int i = 0; i <= res; i++) {
		was[i] = 0;
		visited[i] = 0;
		if (sz(g[i])) g[i].clear();
	}
    cout << '\n';
}
/*
0 2
1 3
3 0

2 1 3 0
*/

signed main() {
    setIO();
    
    int tt = 1;
    if (FLAG) {
    	cin >> tt;
    }
    while (tt--) {
    	solve();
    }
    
    return 0;
}

void setIO(const string &f) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen((f + ".in").c_str(), "r")) {
        freopen((f + ".in").c_str(), "r", stdin);
        freopen((f + ".out").c_str(), "w", stdout);
    }
}

Compilation message

sequence.cpp: In function 'void setIO(const string&)':
sequence.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Ok
2 Correct 4 ms 7372 KB Ok
3 Correct 4 ms 7372 KB Ok
4 Correct 4 ms 7372 KB Ok
5 Correct 4 ms 7376 KB Ok
6 Correct 4 ms 7372 KB Ok
7 Correct 4 ms 7292 KB Ok
8 Correct 4 ms 7372 KB Ok
9 Correct 4 ms 7372 KB Ok
10 Correct 4 ms 7372 KB Ok
11 Correct 6 ms 7372 KB Ok
12 Correct 4 ms 7372 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7268 KB Ok
2 Correct 4 ms 7372 KB Ok
3 Correct 4 ms 7372 KB Ok
4 Correct 5 ms 7372 KB Ok
5 Correct 4 ms 7372 KB Ok
6 Correct 9 ms 7756 KB Ok
7 Correct 22 ms 8688 KB Ok
8 Correct 11 ms 8012 KB Ok
9 Correct 32 ms 8900 KB Ok
10 Correct 15 ms 8280 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Ok
2 Correct 4 ms 7372 KB Ok
3 Correct 4 ms 7372 KB Ok
4 Correct 4 ms 7372 KB Ok
5 Correct 4 ms 7384 KB Ok
6 Correct 341 ms 28268 KB Ok
7 Correct 225 ms 30696 KB Ok
8 Correct 474 ms 33756 KB Ok
9 Correct 355 ms 31984 KB Ok
10 Correct 212 ms 21728 KB Ok
11 Correct 422 ms 33620 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Ok
2 Correct 4 ms 7372 KB Ok
3 Correct 4 ms 7372 KB Ok
4 Correct 4 ms 7372 KB Ok
5 Correct 4 ms 7376 KB Ok
6 Correct 4 ms 7372 KB Ok
7 Correct 4 ms 7292 KB Ok
8 Correct 4 ms 7372 KB Ok
9 Correct 4 ms 7372 KB Ok
10 Correct 4 ms 7372 KB Ok
11 Correct 6 ms 7372 KB Ok
12 Correct 4 ms 7372 KB Ok
13 Correct 4 ms 7372 KB Ok
14 Correct 4 ms 7372 KB Ok
15 Correct 4 ms 7372 KB Ok
16 Correct 3 ms 7372 KB Ok
17 Correct 3 ms 7372 KB Ok
18 Correct 4 ms 7372 KB Ok
19 Correct 4 ms 7372 KB Ok
20 Correct 4 ms 7320 KB Ok
21 Correct 5 ms 7372 KB Ok
22 Correct 4 ms 7372 KB Ok
23 Correct 4 ms 7372 KB Ok
24 Correct 7 ms 7588 KB Ok
25 Correct 9 ms 7628 KB Ok
26 Correct 9 ms 7500 KB Ok
27 Correct 6 ms 7628 KB Ok
28 Correct 8 ms 7556 KB Ok
29 Correct 6 ms 7500 KB Ok
30 Correct 6 ms 7584 KB Ok
31 Correct 6 ms 7628 KB Ok
32 Correct 6 ms 7500 KB Ok
33 Correct 6 ms 7552 KB Ok
34 Correct 13 ms 7952 KB Ok
35 Correct 12 ms 7884 KB Ok
36 Correct 13 ms 7900 KB Ok
37 Correct 12 ms 7884 KB Ok
38 Correct 15 ms 7972 KB Ok
39 Correct 13 ms 7860 KB Ok
40 Correct 13 ms 7864 KB Ok
41 Correct 12 ms 7984 KB Ok
42 Correct 13 ms 7884 KB Ok
43 Correct 12 ms 7884 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Ok
2 Correct 4 ms 7372 KB Ok
3 Correct 4 ms 7372 KB Ok
4 Correct 4 ms 7372 KB Ok
5 Correct 4 ms 7376 KB Ok
6 Correct 4 ms 7372 KB Ok
7 Correct 4 ms 7292 KB Ok
8 Correct 4 ms 7372 KB Ok
9 Correct 4 ms 7372 KB Ok
10 Correct 4 ms 7372 KB Ok
11 Correct 6 ms 7372 KB Ok
12 Correct 4 ms 7372 KB Ok
13 Correct 4 ms 7268 KB Ok
14 Correct 4 ms 7372 KB Ok
15 Correct 4 ms 7372 KB Ok
16 Correct 5 ms 7372 KB Ok
17 Correct 4 ms 7372 KB Ok
18 Correct 9 ms 7756 KB Ok
19 Correct 22 ms 8688 KB Ok
20 Correct 11 ms 8012 KB Ok
21 Correct 32 ms 8900 KB Ok
22 Correct 15 ms 8280 KB Ok
23 Correct 4 ms 7372 KB Ok
24 Correct 4 ms 7372 KB Ok
25 Correct 4 ms 7372 KB Ok
26 Correct 3 ms 7372 KB Ok
27 Correct 3 ms 7372 KB Ok
28 Correct 4 ms 7372 KB Ok
29 Correct 4 ms 7372 KB Ok
30 Correct 4 ms 7320 KB Ok
31 Correct 5 ms 7372 KB Ok
32 Correct 4 ms 7372 KB Ok
33 Correct 4 ms 7372 KB Ok
34 Correct 7 ms 7588 KB Ok
35 Correct 9 ms 7628 KB Ok
36 Correct 9 ms 7500 KB Ok
37 Correct 6 ms 7628 KB Ok
38 Correct 8 ms 7556 KB Ok
39 Correct 6 ms 7500 KB Ok
40 Correct 6 ms 7584 KB Ok
41 Correct 6 ms 7628 KB Ok
42 Correct 6 ms 7500 KB Ok
43 Correct 6 ms 7552 KB Ok
44 Correct 13 ms 7952 KB Ok
45 Correct 12 ms 7884 KB Ok
46 Correct 13 ms 7900 KB Ok
47 Correct 12 ms 7884 KB Ok
48 Correct 15 ms 7972 KB Ok
49 Correct 13 ms 7860 KB Ok
50 Correct 13 ms 7864 KB Ok
51 Correct 12 ms 7984 KB Ok
52 Correct 13 ms 7884 KB Ok
53 Correct 12 ms 7884 KB Ok
54 Correct 144 ms 15176 KB Ok
55 Correct 178 ms 15736 KB Ok
56 Correct 162 ms 15664 KB Ok
57 Correct 128 ms 14420 KB Ok
58 Correct 163 ms 15524 KB Ok
59 Correct 152 ms 15072 KB Ok
60 Correct 141 ms 14464 KB Ok
61 Correct 114 ms 14752 KB Ok
62 Correct 208 ms 15960 KB Ok
63 Correct 151 ms 14804 KB Ok
64 Correct 184 ms 15568 KB Ok
65 Correct 169 ms 15432 KB Ok
66 Correct 134 ms 15100 KB Ok
67 Correct 136 ms 14768 KB Ok
68 Correct 167 ms 15200 KB Ok
69 Correct 862 ms 24420 KB Ok
70 Correct 957 ms 24840 KB Ok
71 Correct 797 ms 24480 KB Ok
72 Correct 805 ms 24332 KB Ok
73 Correct 867 ms 24692 KB Ok
74 Correct 777 ms 24300 KB Ok
75 Correct 725 ms 24452 KB Ok
76 Correct 814 ms 24484 KB Ok
77 Correct 750 ms 24384 KB Ok
78 Correct 869 ms 24304 KB Ok
79 Correct 777 ms 24776 KB Ok
80 Correct 826 ms 24636 KB Ok
81 Correct 764 ms 24700 KB Ok
82 Correct 904 ms 24412 KB Ok
83 Correct 767 ms 24504 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Ok
2 Correct 4 ms 7372 KB Ok
3 Correct 4 ms 7372 KB Ok
4 Correct 4 ms 7372 KB Ok
5 Correct 4 ms 7376 KB Ok
6 Correct 4 ms 7372 KB Ok
7 Correct 4 ms 7292 KB Ok
8 Correct 4 ms 7372 KB Ok
9 Correct 4 ms 7372 KB Ok
10 Correct 4 ms 7372 KB Ok
11 Correct 6 ms 7372 KB Ok
12 Correct 4 ms 7372 KB Ok
13 Correct 4 ms 7268 KB Ok
14 Correct 4 ms 7372 KB Ok
15 Correct 4 ms 7372 KB Ok
16 Correct 5 ms 7372 KB Ok
17 Correct 4 ms 7372 KB Ok
18 Correct 9 ms 7756 KB Ok
19 Correct 22 ms 8688 KB Ok
20 Correct 11 ms 8012 KB Ok
21 Correct 32 ms 8900 KB Ok
22 Correct 15 ms 8280 KB Ok
23 Correct 4 ms 7372 KB Ok
24 Correct 4 ms 7372 KB Ok
25 Correct 4 ms 7372 KB Ok
26 Correct 3 ms 7372 KB Ok
27 Correct 3 ms 7372 KB Ok
28 Correct 4 ms 7372 KB Ok
29 Correct 4 ms 7372 KB Ok
30 Correct 4 ms 7320 KB Ok
31 Correct 5 ms 7372 KB Ok
32 Correct 4 ms 7372 KB Ok
33 Correct 4 ms 7372 KB Ok
34 Correct 5 ms 7372 KB Ok
35 Correct 4 ms 7372 KB Ok
36 Correct 4 ms 7372 KB Ok
37 Correct 4 ms 7372 KB Ok
38 Correct 4 ms 7384 KB Ok
39 Correct 341 ms 28268 KB Ok
40 Correct 225 ms 30696 KB Ok
41 Correct 474 ms 33756 KB Ok
42 Correct 355 ms 31984 KB Ok
43 Correct 212 ms 21728 KB Ok
44 Correct 422 ms 33620 KB Ok
45 Correct 7 ms 7588 KB Ok
46 Correct 9 ms 7628 KB Ok
47 Correct 9 ms 7500 KB Ok
48 Correct 6 ms 7628 KB Ok
49 Correct 8 ms 7556 KB Ok
50 Correct 6 ms 7500 KB Ok
51 Correct 6 ms 7584 KB Ok
52 Correct 6 ms 7628 KB Ok
53 Correct 6 ms 7500 KB Ok
54 Correct 6 ms 7552 KB Ok
55 Correct 13 ms 7952 KB Ok
56 Correct 12 ms 7884 KB Ok
57 Correct 13 ms 7900 KB Ok
58 Correct 12 ms 7884 KB Ok
59 Correct 15 ms 7972 KB Ok
60 Correct 13 ms 7860 KB Ok
61 Correct 13 ms 7864 KB Ok
62 Correct 12 ms 7984 KB Ok
63 Correct 13 ms 7884 KB Ok
64 Correct 12 ms 7884 KB Ok
65 Correct 144 ms 15176 KB Ok
66 Correct 178 ms 15736 KB Ok
67 Correct 162 ms 15664 KB Ok
68 Correct 128 ms 14420 KB Ok
69 Correct 163 ms 15524 KB Ok
70 Correct 152 ms 15072 KB Ok
71 Correct 141 ms 14464 KB Ok
72 Correct 114 ms 14752 KB Ok
73 Correct 208 ms 15960 KB Ok
74 Correct 151 ms 14804 KB Ok
75 Correct 184 ms 15568 KB Ok
76 Correct 169 ms 15432 KB Ok
77 Correct 134 ms 15100 KB Ok
78 Correct 136 ms 14768 KB Ok
79 Correct 167 ms 15200 KB Ok
80 Correct 862 ms 24420 KB Ok
81 Correct 957 ms 24840 KB Ok
82 Correct 797 ms 24480 KB Ok
83 Correct 805 ms 24332 KB Ok
84 Correct 867 ms 24692 KB Ok
85 Correct 777 ms 24300 KB Ok
86 Correct 725 ms 24452 KB Ok
87 Correct 814 ms 24484 KB Ok
88 Correct 750 ms 24384 KB Ok
89 Correct 869 ms 24304 KB Ok
90 Correct 777 ms 24776 KB Ok
91 Correct 826 ms 24636 KB Ok
92 Correct 764 ms 24700 KB Ok
93 Correct 904 ms 24412 KB Ok
94 Correct 767 ms 24504 KB Ok
95 Correct 450 ms 27956 KB Ok
96 Runtime error 160 ms 48780 KB Execution killed with signal 11
97 Halted 0 ms 0 KB -