oj.uz

Submission #497787

# Submission time Handle Problem Language Result Execution time Memory
497787 2021-12-23T20:00:42 Z Ziel Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 66132 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 = 1e6 + 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 = max(n, m) * 2, 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;
			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;
		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 13 ms 23756 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 13 ms 23740 KB Ok
4 Correct 15 ms 23756 KB Ok
5 Correct 13 ms 23708 KB Ok
6 Correct 14 ms 23756 KB Ok
7 Correct 12 ms 23712 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 13 ms 23784 KB Ok
10 Correct 18 ms 23756 KB Ok
11 Correct 13 ms 23756 KB Ok
12 Correct 13 ms 23756 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 14 ms 23720 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 12 ms 23756 KB Ok
5 Correct 12 ms 23756 KB Ok
6 Correct 15 ms 24012 KB Ok
7 Correct 32 ms 25320 KB Ok
8 Correct 22 ms 24480 KB Ok
9 Correct 39 ms 25596 KB Ok
10 Correct 25 ms 24780 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 14 ms 23808 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 13 ms 23776 KB Ok
5 Correct 16 ms 23756 KB Ok
6 Correct 13 ms 23796 KB Ok
7 Correct 12 ms 23692 KB Ok
8 Correct 13 ms 23756 KB Ok
9 Correct 12 ms 23756 KB Ok
10 Correct 14 ms 23740 KB Ok
11 Correct 12 ms 23756 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Ok
2 Correct 14 ms 23756 KB Ok
3 Correct 14 ms 23916 KB Ok
4 Correct 12 ms 23756 KB Ok
5 Correct 13 ms 23756 KB Ok
6 Correct 320 ms 44676 KB Ok
7 Correct 235 ms 47028 KB Ok
8 Correct 505 ms 50216 KB Ok
9 Correct 381 ms 48404 KB Ok
10 Correct 226 ms 38220 KB Ok
11 Correct 515 ms 50144 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 13 ms 23740 KB Ok
4 Correct 15 ms 23756 KB Ok
5 Correct 13 ms 23708 KB Ok
6 Correct 14 ms 23756 KB Ok
7 Correct 12 ms 23712 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 13 ms 23784 KB Ok
10 Correct 18 ms 23756 KB Ok
11 Correct 13 ms 23756 KB Ok
12 Correct 13 ms 23756 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 14 ms 23808 KB Ok
15 Correct 12 ms 23756 KB Ok
16 Correct 13 ms 23776 KB Ok
17 Correct 16 ms 23756 KB Ok
18 Correct 13 ms 23796 KB Ok
19 Correct 12 ms 23692 KB Ok
20 Correct 13 ms 23756 KB Ok
21 Correct 12 ms 23756 KB Ok
22 Correct 14 ms 23740 KB Ok
23 Correct 12 ms 23756 KB Ok
24 Correct 15 ms 24012 KB Ok
25 Correct 16 ms 24100 KB Ok
26 Correct 15 ms 24080 KB Ok
27 Correct 17 ms 24080 KB Ok
28 Correct 15 ms 24012 KB Ok
29 Correct 14 ms 23948 KB Ok
30 Correct 14 ms 24012 KB Ok
31 Correct 15 ms 23992 KB Ok
32 Correct 15 ms 24048 KB Ok
33 Correct 15 ms 23992 KB Ok
34 Correct 20 ms 24324 KB Ok
35 Correct 20 ms 24268 KB Ok
36 Correct 21 ms 24324 KB Ok
37 Correct 21 ms 24288 KB Ok
38 Correct 21 ms 24356 KB Ok
39 Correct 27 ms 24268 KB Ok
40 Correct 21 ms 24376 KB Ok
41 Correct 21 ms 24332 KB Ok
42 Correct 21 ms 24388 KB Ok
43 Correct 21 ms 24344 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 13 ms 23740 KB Ok
4 Correct 15 ms 23756 KB Ok
5 Correct 13 ms 23708 KB Ok
6 Correct 14 ms 23756 KB Ok
7 Correct 12 ms 23712 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 13 ms 23784 KB Ok
10 Correct 18 ms 23756 KB Ok
11 Correct 13 ms 23756 KB Ok
12 Correct 13 ms 23756 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 14 ms 23720 KB Ok
15 Correct 12 ms 23756 KB Ok
16 Correct 12 ms 23756 KB Ok
17 Correct 12 ms 23756 KB Ok
18 Correct 15 ms 24012 KB Ok
19 Correct 32 ms 25320 KB Ok
20 Correct 22 ms 24480 KB Ok
21 Correct 39 ms 25596 KB Ok
22 Correct 25 ms 24780 KB Ok
23 Correct 12 ms 23756 KB Ok
24 Correct 14 ms 23808 KB Ok
25 Correct 12 ms 23756 KB Ok
26 Correct 13 ms 23776 KB Ok
27 Correct 16 ms 23756 KB Ok
28 Correct 13 ms 23796 KB Ok
29 Correct 12 ms 23692 KB Ok
30 Correct 13 ms 23756 KB Ok
31 Correct 12 ms 23756 KB Ok
32 Correct 14 ms 23740 KB Ok
33 Correct 12 ms 23756 KB Ok
34 Correct 15 ms 24012 KB Ok
35 Correct 16 ms 24100 KB Ok
36 Correct 15 ms 24080 KB Ok
37 Correct 17 ms 24080 KB Ok
38 Correct 15 ms 24012 KB Ok
39 Correct 14 ms 23948 KB Ok
40 Correct 14 ms 24012 KB Ok
41 Correct 15 ms 23992 KB Ok
42 Correct 15 ms 24048 KB Ok
43 Correct 15 ms 23992 KB Ok
44 Correct 20 ms 24324 KB Ok
45 Correct 20 ms 24268 KB Ok
46 Correct 21 ms 24324 KB Ok
47 Correct 21 ms 24288 KB Ok
48 Correct 21 ms 24356 KB Ok
49 Correct 27 ms 24268 KB Ok
50 Correct 21 ms 24376 KB Ok
51 Correct 21 ms 24332 KB Ok
52 Correct 21 ms 24388 KB Ok
53 Correct 21 ms 24344 KB Ok
54 Correct 169 ms 31668 KB Ok
55 Correct 201 ms 32184 KB Ok
56 Correct 169 ms 32136 KB Ok
57 Correct 136 ms 30880 KB Ok
58 Correct 164 ms 32140 KB Ok
59 Correct 164 ms 31408 KB Ok
60 Correct 143 ms 30948 KB Ok
61 Correct 129 ms 31300 KB Ok
62 Correct 197 ms 32380 KB Ok
63 Correct 160 ms 31340 KB Ok
64 Correct 199 ms 31992 KB Ok
65 Correct 178 ms 31844 KB Ok
66 Correct 151 ms 31596 KB Ok
67 Correct 132 ms 31348 KB Ok
68 Correct 163 ms 31716 KB Ok
69 Correct 920 ms 40812 KB Ok
70 Correct 1162 ms 41380 KB Ok
71 Correct 741 ms 40904 KB Ok
72 Correct 828 ms 40696 KB Ok
73 Correct 892 ms 41320 KB Ok
74 Correct 846 ms 40792 KB Ok
75 Correct 765 ms 40800 KB Ok
76 Correct 1037 ms 40916 KB Ok
77 Correct 792 ms 40820 KB Ok
78 Correct 1042 ms 40784 KB Ok
79 Correct 1091 ms 41200 KB Ok
80 Correct 891 ms 40752 KB Ok
81 Correct 836 ms 41128 KB Ok
82 Correct 903 ms 40924 KB Ok
83 Correct 737 ms 40872 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Ok
2 Correct 13 ms 23756 KB Ok
3 Correct 13 ms 23740 KB Ok
4 Correct 15 ms 23756 KB Ok
5 Correct 13 ms 23708 KB Ok
6 Correct 14 ms 23756 KB Ok
7 Correct 12 ms 23712 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 13 ms 23784 KB Ok
10 Correct 18 ms 23756 KB Ok
11 Correct 13 ms 23756 KB Ok
12 Correct 13 ms 23756 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 14 ms 23720 KB Ok
15 Correct 12 ms 23756 KB Ok
16 Correct 12 ms 23756 KB Ok
17 Correct 12 ms 23756 KB Ok
18 Correct 15 ms 24012 KB Ok
19 Correct 32 ms 25320 KB Ok
20 Correct 22 ms 24480 KB Ok
21 Correct 39 ms 25596 KB Ok
22 Correct 25 ms 24780 KB Ok
23 Correct 12 ms 23756 KB Ok
24 Correct 14 ms 23808 KB Ok
25 Correct 12 ms 23756 KB Ok
26 Correct 13 ms 23776 KB Ok
27 Correct 16 ms 23756 KB Ok
28 Correct 13 ms 23796 KB Ok
29 Correct 12 ms 23692 KB Ok
30 Correct 13 ms 23756 KB Ok
31 Correct 12 ms 23756 KB Ok
32 Correct 14 ms 23740 KB Ok
33 Correct 12 ms 23756 KB Ok
34 Correct 13 ms 23816 KB Ok
35 Correct 14 ms 23756 KB Ok
36 Correct 14 ms 23916 KB Ok
37 Correct 12 ms 23756 KB Ok
38 Correct 13 ms 23756 KB Ok
39 Correct 320 ms 44676 KB Ok
40 Correct 235 ms 47028 KB Ok
41 Correct 505 ms 50216 KB Ok
42 Correct 381 ms 48404 KB Ok
43 Correct 226 ms 38220 KB Ok
44 Correct 515 ms 50144 KB Ok
45 Correct 15 ms 24012 KB Ok
46 Correct 16 ms 24100 KB Ok
47 Correct 15 ms 24080 KB Ok
48 Correct 17 ms 24080 KB Ok
49 Correct 15 ms 24012 KB Ok
50 Correct 14 ms 23948 KB Ok
51 Correct 14 ms 24012 KB Ok
52 Correct 15 ms 23992 KB Ok
53 Correct 15 ms 24048 KB Ok
54 Correct 15 ms 23992 KB Ok
55 Correct 20 ms 24324 KB Ok
56 Correct 20 ms 24268 KB Ok
57 Correct 21 ms 24324 KB Ok
58 Correct 21 ms 24288 KB Ok
59 Correct 21 ms 24356 KB Ok
60 Correct 27 ms 24268 KB Ok
61 Correct 21 ms 24376 KB Ok
62 Correct 21 ms 24332 KB Ok
63 Correct 21 ms 24388 KB Ok
64 Correct 21 ms 24344 KB Ok
65 Correct 169 ms 31668 KB Ok
66 Correct 201 ms 32184 KB Ok
67 Correct 169 ms 32136 KB Ok
68 Correct 136 ms 30880 KB Ok
69 Correct 164 ms 32140 KB Ok
70 Correct 164 ms 31408 KB Ok
71 Correct 143 ms 30948 KB Ok
72 Correct 129 ms 31300 KB Ok
73 Correct 197 ms 32380 KB Ok
74 Correct 160 ms 31340 KB Ok
75 Correct 199 ms 31992 KB Ok
76 Correct 178 ms 31844 KB Ok
77 Correct 151 ms 31596 KB Ok
78 Correct 132 ms 31348 KB Ok
79 Correct 163 ms 31716 KB Ok
80 Correct 920 ms 40812 KB Ok
81 Correct 1162 ms 41380 KB Ok
82 Correct 741 ms 40904 KB Ok
83 Correct 828 ms 40696 KB Ok
84 Correct 892 ms 41320 KB Ok
85 Correct 846 ms 40792 KB Ok
86 Correct 765 ms 40800 KB Ok
87 Correct 1037 ms 40916 KB Ok
88 Correct 792 ms 40820 KB Ok
89 Correct 1042 ms 40784 KB Ok
90 Correct 1091 ms 41200 KB Ok
91 Correct 891 ms 40752 KB Ok
92 Correct 836 ms 41128 KB Ok
93 Correct 903 ms 40924 KB Ok
94 Correct 737 ms 40872 KB Ok
95 Correct 453 ms 44832 KB Ok
96 Correct 784 ms 55284 KB Ok
97 Correct 741 ms 49568 KB Ok
98 Correct 458 ms 49472 KB Ok
99 Correct 579 ms 48088 KB Ok
100 Correct 651 ms 49440 KB Ok
101 Correct 632 ms 51684 KB Ok
102 Correct 666 ms 49652 KB Ok
103 Correct 643 ms 52144 KB Ok
104 Correct 723 ms 53532 KB Ok
105 Correct 786 ms 56292 KB Ok
106 Correct 557 ms 53236 KB Ok
107 Correct 664 ms 52656 KB Ok
108 Correct 841 ms 55328 KB Ok
109 Correct 669 ms 55080 KB Ok
110 Execution timed out 2072 ms 66132 KB Time limit exceeded
111 Halted 0 ms 0 KB -