oj.uz

Submission #497786

# Submission time Handle Problem Language Result Execution time Memory
497786 2021-12-23T19:59:03 Z Ziel Nice sequence (IZhO18_sequence) C++17
76 / 100
 1053 ms 29892 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 = "");

const int N = 2e5 + 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:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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 + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 3 ms 5036 KB Ok
3 Correct 3 ms 5020 KB Ok
4 Correct 3 ms 5016 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4924 KB Ok
7 Correct 2 ms 4940 KB Ok
8 Correct 3 ms 5024 KB Ok
9 Correct 4 ms 5020 KB Ok
10 Correct 4 ms 4940 KB Ok
11 Correct 4 ms 5024 KB Ok
12 Correct 3 ms 5016 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4996 KB Ok
2 Correct 3 ms 5016 KB Ok
3 Correct 3 ms 5024 KB Ok
4 Correct 3 ms 5024 KB Ok
5 Correct 3 ms 5020 KB Ok
6 Correct 6 ms 5276 KB Ok
7 Correct 25 ms 6336 KB Ok
8 Correct 11 ms 5580 KB Ok
9 Correct 31 ms 6580 KB Ok
10 Correct 16 ms 5908 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 3 ms 5024 KB Ok
3 Correct 3 ms 4940 KB Ok
4 Correct 3 ms 4940 KB Ok
5 Correct 3 ms 5016 KB Ok
6 Correct 390 ms 23364 KB Ok
7 Correct 232 ms 25456 KB Ok
8 Correct 522 ms 27664 KB Ok
9 Correct 389 ms 26732 KB Ok
10 Correct 225 ms 17448 KB Ok
11 Correct 430 ms 28416 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 3 ms 5036 KB Ok
3 Correct 3 ms 5020 KB Ok
4 Correct 3 ms 5016 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4924 KB Ok
7 Correct 2 ms 4940 KB Ok
8 Correct 3 ms 5024 KB Ok
9 Correct 4 ms 5020 KB Ok
10 Correct 4 ms 4940 KB Ok
11 Correct 4 ms 5024 KB Ok
12 Correct 3 ms 5016 KB Ok
13 Correct 3 ms 5020 KB Ok
14 Correct 4 ms 4940 KB Ok
15 Correct 4 ms 4940 KB Ok
16 Correct 3 ms 5020 KB Ok
17 Correct 2 ms 4940 KB Ok
18 Correct 3 ms 4940 KB Ok
19 Correct 3 ms 4940 KB Ok
20 Correct 2 ms 4940 KB Ok
21 Correct 3 ms 4940 KB Ok
22 Correct 3 ms 4940 KB Ok
23 Correct 2 ms 4940 KB Ok
24 Correct 7 ms 5216 KB Ok
25 Correct 6 ms 5196 KB Ok
26 Correct 8 ms 5148 KB Ok
27 Correct 6 ms 5196 KB Ok
28 Correct 5 ms 5080 KB Ok
29 Correct 6 ms 5196 KB Ok
30 Correct 7 ms 5148 KB Ok
31 Correct 6 ms 5196 KB Ok
32 Correct 6 ms 5136 KB Ok
33 Correct 5 ms 5144 KB Ok
34 Correct 11 ms 5480 KB Ok
35 Correct 15 ms 5508 KB Ok
36 Correct 12 ms 5452 KB Ok
37 Correct 13 ms 5508 KB Ok
38 Correct 12 ms 5476 KB Ok
39 Correct 12 ms 5492 KB Ok
40 Correct 14 ms 5516 KB Ok
41 Correct 12 ms 5452 KB Ok
42 Correct 12 ms 5520 KB Ok
43 Correct 12 ms 5452 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 3 ms 5036 KB Ok
3 Correct 3 ms 5020 KB Ok
4 Correct 3 ms 5016 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4924 KB Ok
7 Correct 2 ms 4940 KB Ok
8 Correct 3 ms 5024 KB Ok
9 Correct 4 ms 5020 KB Ok
10 Correct 4 ms 4940 KB Ok
11 Correct 4 ms 5024 KB Ok
12 Correct 3 ms 5016 KB Ok
13 Correct 3 ms 4996 KB Ok
14 Correct 3 ms 5016 KB Ok
15 Correct 3 ms 5024 KB Ok
16 Correct 3 ms 5024 KB Ok
17 Correct 3 ms 5020 KB Ok
18 Correct 6 ms 5276 KB Ok
19 Correct 25 ms 6336 KB Ok
20 Correct 11 ms 5580 KB Ok
21 Correct 31 ms 6580 KB Ok
22 Correct 16 ms 5908 KB Ok
23 Correct 3 ms 5020 KB Ok
24 Correct 4 ms 4940 KB Ok
25 Correct 4 ms 4940 KB Ok
26 Correct 3 ms 5020 KB Ok
27 Correct 2 ms 4940 KB Ok
28 Correct 3 ms 4940 KB Ok
29 Correct 3 ms 4940 KB Ok
30 Correct 2 ms 4940 KB Ok
31 Correct 3 ms 4940 KB Ok
32 Correct 3 ms 4940 KB Ok
33 Correct 2 ms 4940 KB Ok
34 Correct 7 ms 5216 KB Ok
35 Correct 6 ms 5196 KB Ok
36 Correct 8 ms 5148 KB Ok
37 Correct 6 ms 5196 KB Ok
38 Correct 5 ms 5080 KB Ok
39 Correct 6 ms 5196 KB Ok
40 Correct 7 ms 5148 KB Ok
41 Correct 6 ms 5196 KB Ok
42 Correct 6 ms 5136 KB Ok
43 Correct 5 ms 5144 KB Ok
44 Correct 11 ms 5480 KB Ok
45 Correct 15 ms 5508 KB Ok
46 Correct 12 ms 5452 KB Ok
47 Correct 13 ms 5508 KB Ok
48 Correct 12 ms 5476 KB Ok
49 Correct 12 ms 5492 KB Ok
50 Correct 14 ms 5516 KB Ok
51 Correct 12 ms 5452 KB Ok
52 Correct 12 ms 5520 KB Ok
53 Correct 12 ms 5452 KB Ok
54 Correct 150 ms 11484 KB Ok
55 Correct 185 ms 11940 KB Ok
56 Correct 215 ms 11820 KB Ok
57 Correct 127 ms 10816 KB Ok
58 Correct 222 ms 11688 KB Ok
59 Correct 222 ms 11364 KB Ok
60 Correct 136 ms 10836 KB Ok
61 Correct 126 ms 11144 KB Ok
62 Correct 201 ms 12172 KB Ok
63 Correct 155 ms 11148 KB Ok
64 Correct 244 ms 12004 KB Ok
65 Correct 184 ms 11728 KB Ok
66 Correct 181 ms 11356 KB Ok
67 Correct 128 ms 11048 KB Ok
68 Correct 193 ms 11644 KB Ok
69 Correct 1008 ms 20592 KB Ok
70 Correct 1053 ms 21040 KB Ok
71 Correct 768 ms 20648 KB Ok
72 Correct 861 ms 20392 KB Ok
73 Correct 1004 ms 20724 KB Ok
74 Correct 812 ms 20472 KB Ok
75 Correct 745 ms 20444 KB Ok
76 Correct 1031 ms 20548 KB Ok
77 Correct 731 ms 20400 KB Ok
78 Correct 1022 ms 20292 KB Ok
79 Correct 871 ms 20864 KB Ok
80 Correct 854 ms 20536 KB Ok
81 Correct 746 ms 20828 KB Ok
82 Correct 911 ms 20520 KB Ok
83 Correct 749 ms 20696 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Ok
2 Correct 3 ms 5036 KB Ok
3 Correct 3 ms 5020 KB Ok
4 Correct 3 ms 5016 KB Ok
5 Correct 3 ms 4940 KB Ok
6 Correct 3 ms 4924 KB Ok
7 Correct 2 ms 4940 KB Ok
8 Correct 3 ms 5024 KB Ok
9 Correct 4 ms 5020 KB Ok
10 Correct 4 ms 4940 KB Ok
11 Correct 4 ms 5024 KB Ok
12 Correct 3 ms 5016 KB Ok
13 Correct 3 ms 4996 KB Ok
14 Correct 3 ms 5016 KB Ok
15 Correct 3 ms 5024 KB Ok
16 Correct 3 ms 5024 KB Ok
17 Correct 3 ms 5020 KB Ok
18 Correct 6 ms 5276 KB Ok
19 Correct 25 ms 6336 KB Ok
20 Correct 11 ms 5580 KB Ok
21 Correct 31 ms 6580 KB Ok
22 Correct 16 ms 5908 KB Ok
23 Correct 3 ms 5020 KB Ok
24 Correct 4 ms 4940 KB Ok
25 Correct 4 ms 4940 KB Ok
26 Correct 3 ms 5020 KB Ok
27 Correct 2 ms 4940 KB Ok
28 Correct 3 ms 4940 KB Ok
29 Correct 3 ms 4940 KB Ok
30 Correct 2 ms 4940 KB Ok
31 Correct 3 ms 4940 KB Ok
32 Correct 3 ms 4940 KB Ok
33 Correct 2 ms 4940 KB Ok
34 Correct 3 ms 4940 KB Ok
35 Correct 3 ms 5024 KB Ok
36 Correct 3 ms 4940 KB Ok
37 Correct 3 ms 4940 KB Ok
38 Correct 3 ms 5016 KB Ok
39 Correct 390 ms 23364 KB Ok
40 Correct 232 ms 25456 KB Ok
41 Correct 522 ms 27664 KB Ok
42 Correct 389 ms 26732 KB Ok
43 Correct 225 ms 17448 KB Ok
44 Correct 430 ms 28416 KB Ok
45 Correct 7 ms 5216 KB Ok
46 Correct 6 ms 5196 KB Ok
47 Correct 8 ms 5148 KB Ok
48 Correct 6 ms 5196 KB Ok
49 Correct 5 ms 5080 KB Ok
50 Correct 6 ms 5196 KB Ok
51 Correct 7 ms 5148 KB Ok
52 Correct 6 ms 5196 KB Ok
53 Correct 6 ms 5136 KB Ok
54 Correct 5 ms 5144 KB Ok
55 Correct 11 ms 5480 KB Ok
56 Correct 15 ms 5508 KB Ok
57 Correct 12 ms 5452 KB Ok
58 Correct 13 ms 5508 KB Ok
59 Correct 12 ms 5476 KB Ok
60 Correct 12 ms 5492 KB Ok
61 Correct 14 ms 5516 KB Ok
62 Correct 12 ms 5452 KB Ok
63 Correct 12 ms 5520 KB Ok
64 Correct 12 ms 5452 KB Ok
65 Correct 150 ms 11484 KB Ok
66 Correct 185 ms 11940 KB Ok
67 Correct 215 ms 11820 KB Ok
68 Correct 127 ms 10816 KB Ok
69 Correct 222 ms 11688 KB Ok
70 Correct 222 ms 11364 KB Ok
71 Correct 136 ms 10836 KB Ok
72 Correct 126 ms 11144 KB Ok
73 Correct 201 ms 12172 KB Ok
74 Correct 155 ms 11148 KB Ok
75 Correct 244 ms 12004 KB Ok
76 Correct 184 ms 11728 KB Ok
77 Correct 181 ms 11356 KB Ok
78 Correct 128 ms 11048 KB Ok
79 Correct 193 ms 11644 KB Ok
80 Correct 1008 ms 20592 KB Ok
81 Correct 1053 ms 21040 KB Ok
82 Correct 768 ms 20648 KB Ok
83 Correct 861 ms 20392 KB Ok
84 Correct 1004 ms 20724 KB Ok
85 Correct 812 ms 20472 KB Ok
86 Correct 745 ms 20444 KB Ok
87 Correct 1031 ms 20548 KB Ok
88 Correct 731 ms 20400 KB Ok
89 Correct 1022 ms 20292 KB Ok
90 Correct 871 ms 20864 KB Ok
91 Correct 854 ms 20536 KB Ok
92 Correct 746 ms 20828 KB Ok
93 Correct 911 ms 20520 KB Ok
94 Correct 749 ms 20696 KB Ok
95 Runtime error 159 ms 29892 KB Execution killed with signal 11
96 Halted 0 ms 0 KB -