oj.uz

Submission #237487

# Submission time Handle Problem Language Result Execution time Memory
237487 2020-06-07T02:22:05 Z _7_7_ Nice sequence (IZhO18_sequence) C++14
100 / 100
 1491 ms 64168 KB 
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 4e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


int T, n, m, timer, t[N], p[N];
bool cycle, rev;
vi g[N];

int get (int v) {
	return v == p[v] ? v : p[v] = get(p[v]);
}

void merge (int v, int u) {
    v = get(v);
    u = get(u);

	if (rand() & 1)
		swap(v, u);
	p[u] = v;
}


void dfs (int v) {
	for (auto to : g[v]) 
		if (!t[to])  
			dfs(to);
	
	t[v] = ++timer;
}

	
inline bool check (int k) {
    for (int i = 0; i <= k; ++i) 
    	g[i].clear();
    

	for (int i = 0; i <= k; ++i) {
		t[i] = 0; 
		if (i - n >= 0)
			g[i - n].pb(i);
		if (i - m >= 0)
			g[i].pb(i - m);
	}



	timer = 0;
	cycle = 0;

	for (int i = 0; i <= k && !cycle; ++i)
		if (!t[i])
			dfs(i);

	return cycle ^ 1;

}

main () {
	cin >> T;
	while (T--) {
		cin >> n >> m;		
		rev = 0;
		if (n < m) {
			swap(n, m);
			rev = 1;
		}

		for (int i = 0; i < m; ++i)
			p[i] = i;

		int res = 0;
		while (1) {
			++res;
			if (res >= n) {
				if (get(res % m) == get((res - n) % m))
					break;
				merge(res % m, (res - n) % m);
			}
		}

		--res;

		if (rev)
			swap(n, m);
		check(res);
		printf("%d\n", res);
		for (int i = 1; i <= res; ++i)
			printf("%d ", t[i] - t[i - 1]);
		printf("\n");
	}
}

Compilation message

sequence.cpp: In function 'bool check(int)':
sequence.cpp:69:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i <= k; ++i) 
     ^~~
sequence.cpp:73:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i = 0; i <= k; ++i) {
  ^~~
sequence.cpp: At global scope:
sequence.cpp:94:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Ok
2 Correct 11 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 12 ms 9856 KB Ok
7 Correct 21 ms 10624 KB Ok
8 Correct 15 ms 10112 KB Ok
9 Correct 22 ms 10752 KB Ok
10 Correct 17 ms 10368 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Ok
2 Correct 11 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 131 ms 21368 KB Ok
7 Correct 119 ms 25336 KB Ok
8 Correct 210 ms 28280 KB Ok
9 Correct 159 ms 25848 KB Ok
10 Correct 94 ms 18168 KB Ok
11 Correct 151 ms 23544 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 10 ms 9728 KB Ok
8 Correct 11 ms 9728 KB Ok
9 Correct 10 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 10 ms 9728 KB Ok
12 Correct 10 ms 9728 KB Ok
13 Correct 11 ms 9728 KB Ok
14 Correct 10 ms 9728 KB Ok
15 Correct 10 ms 9728 KB Ok
16 Correct 10 ms 9728 KB Ok
17 Correct 11 ms 9728 KB Ok
18 Correct 11 ms 9808 KB Ok
19 Correct 10 ms 9728 KB Ok
20 Correct 10 ms 9728 KB Ok
21 Correct 10 ms 9728 KB Ok
22 Correct 10 ms 9728 KB Ok
23 Correct 10 ms 9728 KB Ok
24 Correct 12 ms 9856 KB Ok
25 Correct 12 ms 9856 KB Ok
26 Correct 12 ms 9856 KB Ok
27 Correct 12 ms 9856 KB Ok
28 Correct 12 ms 9856 KB Ok
29 Correct 12 ms 9856 KB Ok
30 Correct 13 ms 9856 KB Ok
31 Correct 12 ms 9856 KB Ok
32 Correct 12 ms 9856 KB Ok
33 Correct 12 ms 9856 KB Ok
34 Correct 15 ms 10112 KB Ok
35 Correct 15 ms 10112 KB Ok
36 Correct 15 ms 10112 KB Ok
37 Correct 15 ms 10112 KB Ok
38 Correct 16 ms 10112 KB Ok
39 Correct 15 ms 9984 KB Ok
40 Correct 15 ms 10112 KB Ok
41 Correct 15 ms 10112 KB Ok
42 Correct 15 ms 10112 KB Ok
43 Correct 15 ms 10112 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 10 ms 9728 KB Ok
8 Correct 11 ms 9728 KB Ok
9 Correct 10 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 10 ms 9728 KB Ok
12 Correct 10 ms 9728 KB Ok
13 Correct 10 ms 9728 KB Ok
14 Correct 11 ms 9728 KB Ok
15 Correct 10 ms 9728 KB Ok
16 Correct 10 ms 9728 KB Ok
17 Correct 10 ms 9728 KB Ok
18 Correct 12 ms 9856 KB Ok
19 Correct 21 ms 10624 KB Ok
20 Correct 15 ms 10112 KB Ok
21 Correct 22 ms 10752 KB Ok
22 Correct 17 ms 10368 KB Ok
23 Correct 11 ms 9728 KB Ok
24 Correct 10 ms 9728 KB Ok
25 Correct 10 ms 9728 KB Ok
26 Correct 10 ms 9728 KB Ok
27 Correct 11 ms 9728 KB Ok
28 Correct 11 ms 9808 KB Ok
29 Correct 10 ms 9728 KB Ok
30 Correct 10 ms 9728 KB Ok
31 Correct 10 ms 9728 KB Ok
32 Correct 10 ms 9728 KB Ok
33 Correct 10 ms 9728 KB Ok
34 Correct 12 ms 9856 KB Ok
35 Correct 12 ms 9856 KB Ok
36 Correct 12 ms 9856 KB Ok
37 Correct 12 ms 9856 KB Ok
38 Correct 12 ms 9856 KB Ok
39 Correct 12 ms 9856 KB Ok
40 Correct 13 ms 9856 KB Ok
41 Correct 12 ms 9856 KB Ok
42 Correct 12 ms 9856 KB Ok
43 Correct 12 ms 9856 KB Ok
44 Correct 15 ms 10112 KB Ok
45 Correct 15 ms 10112 KB Ok
46 Correct 15 ms 10112 KB Ok
47 Correct 15 ms 10112 KB Ok
48 Correct 16 ms 10112 KB Ok
49 Correct 15 ms 9984 KB Ok
50 Correct 15 ms 10112 KB Ok
51 Correct 15 ms 10112 KB Ok
52 Correct 15 ms 10112 KB Ok
53 Correct 15 ms 10112 KB Ok
54 Correct 98 ms 14840 KB Ok
55 Correct 119 ms 15096 KB Ok
56 Correct 115 ms 15224 KB Ok
57 Correct 82 ms 14328 KB Ok
58 Correct 98 ms 14564 KB Ok
59 Correct 96 ms 14328 KB Ok
60 Correct 83 ms 13944 KB Ok
61 Correct 86 ms 14584 KB Ok
62 Correct 113 ms 14968 KB Ok
63 Correct 89 ms 14328 KB Ok
64 Correct 109 ms 15224 KB Ok
65 Correct 103 ms 14712 KB Ok
66 Correct 94 ms 14584 KB Ok
67 Correct 88 ms 14328 KB Ok
68 Correct 95 ms 14712 KB Ok
69 Correct 214 ms 22392 KB Ok
70 Correct 235 ms 23288 KB Ok
71 Correct 244 ms 22664 KB Ok
72 Correct 218 ms 22520 KB Ok
73 Correct 229 ms 21980 KB Ok
74 Correct 248 ms 21752 KB Ok
75 Correct 218 ms 21752 KB Ok
76 Correct 218 ms 22648 KB Ok
77 Correct 247 ms 21496 KB Ok
78 Correct 217 ms 21752 KB Ok
79 Correct 233 ms 22392 KB Ok
80 Correct 276 ms 22520 KB Ok
81 Correct 215 ms 22008 KB Ok
82 Correct 224 ms 22264 KB Ok
83 Correct 218 ms 21752 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Ok
2 Correct 10 ms 9728 KB Ok
3 Correct 10 ms 9728 KB Ok
4 Correct 10 ms 9728 KB Ok
5 Correct 10 ms 9728 KB Ok
6 Correct 10 ms 9728 KB Ok
7 Correct 10 ms 9728 KB Ok
8 Correct 11 ms 9728 KB Ok
9 Correct 10 ms 9728 KB Ok
10 Correct 10 ms 9728 KB Ok
11 Correct 10 ms 9728 KB Ok
12 Correct 10 ms 9728 KB Ok
13 Correct 10 ms 9728 KB Ok
14 Correct 11 ms 9728 KB Ok
15 Correct 10 ms 9728 KB Ok
16 Correct 10 ms 9728 KB Ok
17 Correct 10 ms 9728 KB Ok
18 Correct 12 ms 9856 KB Ok
19 Correct 21 ms 10624 KB Ok
20 Correct 15 ms 10112 KB Ok
21 Correct 22 ms 10752 KB Ok
22 Correct 17 ms 10368 KB Ok
23 Correct 11 ms 9728 KB Ok
24 Correct 10 ms 9728 KB Ok
25 Correct 10 ms 9728 KB Ok
26 Correct 10 ms 9728 KB Ok
27 Correct 11 ms 9728 KB Ok
28 Correct 11 ms 9808 KB Ok
29 Correct 10 ms 9728 KB Ok
30 Correct 10 ms 9728 KB Ok
31 Correct 10 ms 9728 KB Ok
32 Correct 10 ms 9728 KB Ok
33 Correct 10 ms 9728 KB Ok
34 Correct 10 ms 9728 KB Ok
35 Correct 11 ms 9728 KB Ok
36 Correct 10 ms 9728 KB Ok
37 Correct 10 ms 9728 KB Ok
38 Correct 10 ms 9728 KB Ok
39 Correct 131 ms 21368 KB Ok
40 Correct 119 ms 25336 KB Ok
41 Correct 210 ms 28280 KB Ok
42 Correct 159 ms 25848 KB Ok
43 Correct 94 ms 18168 KB Ok
44 Correct 151 ms 23544 KB Ok
45 Correct 12 ms 9856 KB Ok
46 Correct 12 ms 9856 KB Ok
47 Correct 12 ms 9856 KB Ok
48 Correct 12 ms 9856 KB Ok
49 Correct 12 ms 9856 KB Ok
50 Correct 12 ms 9856 KB Ok
51 Correct 13 ms 9856 KB Ok
52 Correct 12 ms 9856 KB Ok
53 Correct 12 ms 9856 KB Ok
54 Correct 12 ms 9856 KB Ok
55 Correct 15 ms 10112 KB Ok
56 Correct 15 ms 10112 KB Ok
57 Correct 15 ms 10112 KB Ok
58 Correct 15 ms 10112 KB Ok
59 Correct 16 ms 10112 KB Ok
60 Correct 15 ms 9984 KB Ok
61 Correct 15 ms 10112 KB Ok
62 Correct 15 ms 10112 KB Ok
63 Correct 15 ms 10112 KB Ok
64 Correct 15 ms 10112 KB Ok
65 Correct 98 ms 14840 KB Ok
66 Correct 119 ms 15096 KB Ok
67 Correct 115 ms 15224 KB Ok
68 Correct 82 ms 14328 KB Ok
69 Correct 98 ms 14564 KB Ok
70 Correct 96 ms 14328 KB Ok
71 Correct 83 ms 13944 KB Ok
72 Correct 86 ms 14584 KB Ok
73 Correct 113 ms 14968 KB Ok
74 Correct 89 ms 14328 KB Ok
75 Correct 109 ms 15224 KB Ok
76 Correct 103 ms 14712 KB Ok
77 Correct 94 ms 14584 KB Ok
78 Correct 88 ms 14328 KB Ok
79 Correct 95 ms 14712 KB Ok
80 Correct 214 ms 22392 KB Ok
81 Correct 235 ms 23288 KB Ok
82 Correct 244 ms 22664 KB Ok
83 Correct 218 ms 22520 KB Ok
84 Correct 229 ms 21980 KB Ok
85 Correct 248 ms 21752 KB Ok
86 Correct 218 ms 21752 KB Ok
87 Correct 218 ms 22648 KB Ok
88 Correct 247 ms 21496 KB Ok
89 Correct 217 ms 21752 KB Ok
90 Correct 233 ms 22392 KB Ok
91 Correct 276 ms 22520 KB Ok
92 Correct 215 ms 22008 KB Ok
93 Correct 224 ms 22264 KB Ok
94 Correct 218 ms 21752 KB Ok
95 Correct 233 ms 22904 KB Ok
96 Correct 338 ms 28588 KB Ok
97 Correct 319 ms 25312 KB Ok
98 Correct 230 ms 25336 KB Ok
99 Correct 280 ms 24824 KB Ok
100 Correct 289 ms 24440 KB Ok
101 Correct 293 ms 27128 KB Ok
102 Correct 285 ms 25848 KB Ok
103 Correct 288 ms 26364 KB Ok
104 Correct 350 ms 28152 KB Ok
105 Correct 352 ms 28280 KB Ok
106 Correct 300 ms 28512 KB Ok
107 Correct 303 ms 27568 KB Ok
108 Correct 364 ms 28408 KB Ok
109 Correct 331 ms 29368 KB Ok
110 Correct 1134 ms 61176 KB Ok
111 Correct 1278 ms 63480 KB Ok
112 Correct 1269 ms 61048 KB Ok
113 Correct 1225 ms 63736 KB Ok
114 Correct 1262 ms 64168 KB Ok
115 Correct 1286 ms 61432 KB Ok
116 Correct 1310 ms 63744 KB Ok
117 Correct 1191 ms 62840 KB Ok
118 Correct 1374 ms 63224 KB Ok
119 Correct 1217 ms 62456 KB Ok
120 Correct 1210 ms 62456 KB Ok
121 Correct 1364 ms 61904 KB Ok
122 Correct 1221 ms 62200 KB Ok
123 Correct 1491 ms 63908 KB Ok
124 Correct 1178 ms 58884 KB Ok
125 Correct 556 ms 47272 KB Ok