oj.uz

Submission #497791

# Submission time Handle Problem Language Result Execution time Memory
497791 2021-12-23T20:09:11 Z Ziel Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 66044 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 = 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;
		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 15 ms 23756 KB Ok
2 Correct 16 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 12 ms 23820 KB Ok
5 Correct 12 ms 23768 KB Ok
6 Correct 11 ms 23820 KB Ok
7 Correct 13 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 12 ms 23736 KB Ok
10 Correct 12 ms 23772 KB Ok
11 Correct 43 ms 23808 KB Ok
12 Correct 46 ms 23720 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 13 ms 23820 KB Ok
3 Correct 17 ms 23824 KB Ok
4 Correct 15 ms 23756 KB Ok
5 Correct 16 ms 23756 KB Ok
6 Correct 48 ms 24004 KB Ok
7 Correct 32 ms 25116 KB Ok
8 Correct 19 ms 24396 KB Ok
9 Correct 54 ms 25400 KB Ok
10 Correct 23 ms 24592 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Ok
2 Correct 12 ms 23756 KB Ok
3 Correct 11 ms 23756 KB Ok
4 Correct 11 ms 23756 KB Ok
5 Correct 12 ms 23728 KB Ok
6 Correct 12 ms 23756 KB Ok
7 Correct 13 ms 23808 KB Ok
8 Correct 53 ms 23716 KB Ok
9 Correct 14 ms 23756 KB Ok
10 Correct 11 ms 23748 KB Ok
11 Correct 15 ms 23816 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Ok
2 Correct 32 ms 23776 KB Ok
3 Correct 14 ms 23772 KB Ok
4 Correct 13 ms 23708 KB Ok
5 Correct 13 ms 23820 KB Ok
6 Correct 389 ms 44616 KB Ok
7 Correct 305 ms 47040 KB Ok
8 Correct 515 ms 50272 KB Ok
9 Correct 454 ms 48504 KB Ok
10 Correct 240 ms 38156 KB Ok
11 Correct 472 ms 50056 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Ok
2 Correct 16 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 12 ms 23820 KB Ok
5 Correct 12 ms 23768 KB Ok
6 Correct 11 ms 23820 KB Ok
7 Correct 13 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 12 ms 23736 KB Ok
10 Correct 12 ms 23772 KB Ok
11 Correct 43 ms 23808 KB Ok
12 Correct 46 ms 23720 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 12 ms 23756 KB Ok
15 Correct 11 ms 23756 KB Ok
16 Correct 11 ms 23756 KB Ok
17 Correct 12 ms 23728 KB Ok
18 Correct 12 ms 23756 KB Ok
19 Correct 13 ms 23808 KB Ok
20 Correct 53 ms 23716 KB Ok
21 Correct 14 ms 23756 KB Ok
22 Correct 11 ms 23748 KB Ok
23 Correct 15 ms 23816 KB Ok
24 Correct 13 ms 24040 KB Ok
25 Correct 18 ms 24012 KB Ok
26 Correct 19 ms 24052 KB Ok
27 Correct 19 ms 24072 KB Ok
28 Correct 17 ms 24028 KB Ok
29 Correct 15 ms 24012 KB Ok
30 Correct 14 ms 24012 KB Ok
31 Correct 18 ms 23996 KB Ok
32 Correct 15 ms 23992 KB Ok
33 Correct 14 ms 24076 KB Ok
34 Correct 22 ms 24308 KB Ok
35 Correct 22 ms 24268 KB Ok
36 Correct 25 ms 24396 KB Ok
37 Correct 23 ms 24348 KB Ok
38 Correct 24 ms 24396 KB Ok
39 Correct 19 ms 24316 KB Ok
40 Correct 20 ms 24300 KB Ok
41 Correct 21 ms 24428 KB Ok
42 Correct 21 ms 24388 KB Ok
43 Correct 25 ms 24396 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Ok
2 Correct 16 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 12 ms 23820 KB Ok
5 Correct 12 ms 23768 KB Ok
6 Correct 11 ms 23820 KB Ok
7 Correct 13 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 12 ms 23736 KB Ok
10 Correct 12 ms 23772 KB Ok
11 Correct 43 ms 23808 KB Ok
12 Correct 46 ms 23720 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 13 ms 23820 KB Ok
15 Correct 17 ms 23824 KB Ok
16 Correct 15 ms 23756 KB Ok
17 Correct 16 ms 23756 KB Ok
18 Correct 48 ms 24004 KB Ok
19 Correct 32 ms 25116 KB Ok
20 Correct 19 ms 24396 KB Ok
21 Correct 54 ms 25400 KB Ok
22 Correct 23 ms 24592 KB Ok
23 Correct 12 ms 23756 KB Ok
24 Correct 12 ms 23756 KB Ok
25 Correct 11 ms 23756 KB Ok
26 Correct 11 ms 23756 KB Ok
27 Correct 12 ms 23728 KB Ok
28 Correct 12 ms 23756 KB Ok
29 Correct 13 ms 23808 KB Ok
30 Correct 53 ms 23716 KB Ok
31 Correct 14 ms 23756 KB Ok
32 Correct 11 ms 23748 KB Ok
33 Correct 15 ms 23816 KB Ok
34 Correct 13 ms 24040 KB Ok
35 Correct 18 ms 24012 KB Ok
36 Correct 19 ms 24052 KB Ok
37 Correct 19 ms 24072 KB Ok
38 Correct 17 ms 24028 KB Ok
39 Correct 15 ms 24012 KB Ok
40 Correct 14 ms 24012 KB Ok
41 Correct 18 ms 23996 KB Ok
42 Correct 15 ms 23992 KB Ok
43 Correct 14 ms 24076 KB Ok
44 Correct 22 ms 24308 KB Ok
45 Correct 22 ms 24268 KB Ok
46 Correct 25 ms 24396 KB Ok
47 Correct 23 ms 24348 KB Ok
48 Correct 24 ms 24396 KB Ok
49 Correct 19 ms 24316 KB Ok
50 Correct 20 ms 24300 KB Ok
51 Correct 21 ms 24428 KB Ok
52 Correct 21 ms 24388 KB Ok
53 Correct 25 ms 24396 KB Ok
54 Correct 182 ms 31656 KB Ok
55 Correct 196 ms 32232 KB Ok
56 Correct 209 ms 32180 KB Ok
57 Correct 162 ms 30780 KB Ok
58 Correct 182 ms 31968 KB Ok
59 Correct 162 ms 31408 KB Ok
60 Correct 185 ms 30844 KB Ok
61 Correct 129 ms 31200 KB Ok
62 Correct 217 ms 32284 KB Ok
63 Correct 164 ms 31264 KB Ok
64 Correct 235 ms 31980 KB Ok
65 Correct 183 ms 31828 KB Ok
66 Correct 203 ms 31492 KB Ok
67 Correct 191 ms 31176 KB Ok
68 Correct 200 ms 31636 KB Ok
69 Correct 1288 ms 40836 KB Ok
70 Correct 960 ms 41280 KB Ok
71 Correct 1048 ms 40880 KB Ok
72 Correct 1127 ms 40700 KB Ok
73 Correct 1131 ms 41020 KB Ok
74 Correct 1053 ms 40744 KB Ok
75 Correct 1031 ms 40812 KB Ok
76 Correct 1303 ms 40924 KB Ok
77 Correct 910 ms 40832 KB Ok
78 Correct 1056 ms 40732 KB Ok
79 Correct 988 ms 41212 KB Ok
80 Correct 847 ms 40796 KB Ok
81 Correct 897 ms 41196 KB Ok
82 Correct 1008 ms 40848 KB Ok
83 Correct 851 ms 40880 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Ok
2 Correct 16 ms 23756 KB Ok
3 Correct 12 ms 23756 KB Ok
4 Correct 12 ms 23820 KB Ok
5 Correct 12 ms 23768 KB Ok
6 Correct 11 ms 23820 KB Ok
7 Correct 13 ms 23756 KB Ok
8 Correct 12 ms 23756 KB Ok
9 Correct 12 ms 23736 KB Ok
10 Correct 12 ms 23772 KB Ok
11 Correct 43 ms 23808 KB Ok
12 Correct 46 ms 23720 KB Ok
13 Correct 12 ms 23756 KB Ok
14 Correct 13 ms 23820 KB Ok
15 Correct 17 ms 23824 KB Ok
16 Correct 15 ms 23756 KB Ok
17 Correct 16 ms 23756 KB Ok
18 Correct 48 ms 24004 KB Ok
19 Correct 32 ms 25116 KB Ok
20 Correct 19 ms 24396 KB Ok
21 Correct 54 ms 25400 KB Ok
22 Correct 23 ms 24592 KB Ok
23 Correct 12 ms 23756 KB Ok
24 Correct 12 ms 23756 KB Ok
25 Correct 11 ms 23756 KB Ok
26 Correct 11 ms 23756 KB Ok
27 Correct 12 ms 23728 KB Ok
28 Correct 12 ms 23756 KB Ok
29 Correct 13 ms 23808 KB Ok
30 Correct 53 ms 23716 KB Ok
31 Correct 14 ms 23756 KB Ok
32 Correct 11 ms 23748 KB Ok
33 Correct 15 ms 23816 KB Ok
34 Correct 15 ms 23756 KB Ok
35 Correct 32 ms 23776 KB Ok
36 Correct 14 ms 23772 KB Ok
37 Correct 13 ms 23708 KB Ok
38 Correct 13 ms 23820 KB Ok
39 Correct 389 ms 44616 KB Ok
40 Correct 305 ms 47040 KB Ok
41 Correct 515 ms 50272 KB Ok
42 Correct 454 ms 48504 KB Ok
43 Correct 240 ms 38156 KB Ok
44 Correct 472 ms 50056 KB Ok
45 Correct 13 ms 24040 KB Ok
46 Correct 18 ms 24012 KB Ok
47 Correct 19 ms 24052 KB Ok
48 Correct 19 ms 24072 KB Ok
49 Correct 17 ms 24028 KB Ok
50 Correct 15 ms 24012 KB Ok
51 Correct 14 ms 24012 KB Ok
52 Correct 18 ms 23996 KB Ok
53 Correct 15 ms 23992 KB Ok
54 Correct 14 ms 24076 KB Ok
55 Correct 22 ms 24308 KB Ok
56 Correct 22 ms 24268 KB Ok
57 Correct 25 ms 24396 KB Ok
58 Correct 23 ms 24348 KB Ok
59 Correct 24 ms 24396 KB Ok
60 Correct 19 ms 24316 KB Ok
61 Correct 20 ms 24300 KB Ok
62 Correct 21 ms 24428 KB Ok
63 Correct 21 ms 24388 KB Ok
64 Correct 25 ms 24396 KB Ok
65 Correct 182 ms 31656 KB Ok
66 Correct 196 ms 32232 KB Ok
67 Correct 209 ms 32180 KB Ok
68 Correct 162 ms 30780 KB Ok
69 Correct 182 ms 31968 KB Ok
70 Correct 162 ms 31408 KB Ok
71 Correct 185 ms 30844 KB Ok
72 Correct 129 ms 31200 KB Ok
73 Correct 217 ms 32284 KB Ok
74 Correct 164 ms 31264 KB Ok
75 Correct 235 ms 31980 KB Ok
76 Correct 183 ms 31828 KB Ok
77 Correct 203 ms 31492 KB Ok
78 Correct 191 ms 31176 KB Ok
79 Correct 200 ms 31636 KB Ok
80 Correct 1288 ms 40836 KB Ok
81 Correct 960 ms 41280 KB Ok
82 Correct 1048 ms 40880 KB Ok
83 Correct 1127 ms 40700 KB Ok
84 Correct 1131 ms 41020 KB Ok
85 Correct 1053 ms 40744 KB Ok
86 Correct 1031 ms 40812 KB Ok
87 Correct 1303 ms 40924 KB Ok
88 Correct 910 ms 40832 KB Ok
89 Correct 1056 ms 40732 KB Ok
90 Correct 988 ms 41212 KB Ok
91 Correct 847 ms 40796 KB Ok
92 Correct 897 ms 41196 KB Ok
93 Correct 1008 ms 40848 KB Ok
94 Correct 851 ms 40880 KB Ok
95 Correct 507 ms 44360 KB Ok
96 Correct 908 ms 55012 KB Ok
97 Correct 769 ms 49180 KB Ok
98 Correct 507 ms 48408 KB Ok
99 Correct 643 ms 48172 KB Ok
100 Correct 722 ms 48312 KB Ok
101 Correct 643 ms 51328 KB Ok
102 Correct 683 ms 49772 KB Ok
103 Correct 762 ms 51168 KB Ok
104 Correct 802 ms 52772 KB Ok
105 Correct 865 ms 55976 KB Ok
106 Correct 660 ms 52940 KB Ok
107 Correct 774 ms 52568 KB Ok
108 Correct 863 ms 54616 KB Ok
109 Correct 693 ms 54824 KB Ok
110 Execution timed out 2070 ms 66044 KB Time limit exceeded
111 Halted 0 ms 0 KB -