oj.uz

Submission #334961

# Submission time Handle Problem Language Result Execution time Memory
334961 2020-12-10T13:03:20 Z amunduzbaev Nice sequence (IZhO18_sequence) C++14
100 / 100
 1982 ms 45404 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long 
#define ld long double 
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define prc(n) fixed << setprecision(n)
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi acos(-1);
const int inf = 1e9 + 7;
const int N = 1e6 + 5;
 
int len, n, m, pref[N];
bool vis[N];
vector<int>top;
 
void dfs(int v){
	vis[v] = 1;
    if(v - m >= 0 && !vis[v - m]) dfs(v - m);
    if(v + n <= len && !vis[v + n]) dfs(v + n);
    top.push_back(v);
}
 
bool check(int x){
	len=x;
    top.clear();
    for(int i = 0; i <= len; i++) vis[i] = 0;
    for(int i = 0; i <= len; i++) if(!vis[i]) dfs(i);
    for(int i = 0; i <= len; i++) pref[ top[i] ] = i;
    for(int i = 0; i <= len; i++){
        if(i - m >= 0 && pref[i] <= pref[i - m]) return false;
        if(i + n <= len && pref[i] <= pref[i + n]) return false;
    }
    return true;
}
 
void solve(){
	scanf("%d %d", &n, &m);
	int l = 0, r = 400000;
	
	while(l < r){
		int mid = (l+r+1) >> 1;
		if(check(mid)) l = mid;
		else r = mid-1;
	}
	check(l);
  printf("%d\n", l);
	if(l){
		for(int i=1;i<=l;i++) printf("%d ", pref[i] - pref[i-1]);
		printf("\n");
	}
	return;
}
 
int main(){
	int t;
	scanf("%d", &t);
	while(t--) solve();
	return 0;
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2656 KB Ok
4 Correct 52 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 63 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 54 ms 5372 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 58 ms 2400 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8416 KB Ok
2 Correct 73 ms 8416 KB Ok
3 Correct 64 ms 8416 KB Ok
4 Correct 68 ms 8428 KB Ok
5 Correct 72 ms 8416 KB Ok
6 Correct 64 ms 8544 KB Ok
7 Correct 84 ms 8820 KB Ok
8 Correct 78 ms 8672 KB Ok
9 Correct 121 ms 8972 KB Ok
10 Correct 79 ms 8928 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8544 KB Ok
2 Correct 73 ms 8416 KB Ok
3 Correct 66 ms 8448 KB Ok
4 Correct 75 ms 8416 KB Ok
5 Correct 73 ms 8416 KB Ok
6 Correct 81 ms 8544 KB Ok
7 Correct 69 ms 8416 KB Ok
8 Correct 78 ms 8416 KB Ok
9 Correct 71 ms 8500 KB Ok
10 Correct 76 ms 8416 KB Ok
11 Correct 77 ms 8544 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8416 KB Ok
2 Correct 87 ms 8416 KB Ok
3 Correct 87 ms 8416 KB Ok
4 Correct 90 ms 8416 KB Ok
5 Correct 80 ms 8416 KB Ok
6 Correct 435 ms 11984 KB Ok
7 Correct 355 ms 10564 KB Ok
8 Correct 655 ms 14024 KB Ok
9 Correct 478 ms 13024 KB Ok
10 Correct 288 ms 9952 KB Ok
11 Correct 425 ms 12128 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2656 KB Ok
4 Correct 52 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 63 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 54 ms 5372 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 58 ms 2400 KB Ok
13 Correct 30 ms 8544 KB Ok
14 Correct 73 ms 8416 KB Ok
15 Correct 66 ms 8448 KB Ok
16 Correct 75 ms 8416 KB Ok
17 Correct 73 ms 8416 KB Ok
18 Correct 81 ms 8544 KB Ok
19 Correct 69 ms 8416 KB Ok
20 Correct 78 ms 8416 KB Ok
21 Correct 71 ms 8500 KB Ok
22 Correct 76 ms 8416 KB Ok
23 Correct 77 ms 8544 KB Ok
24 Correct 64 ms 2272 KB Ok
25 Correct 63 ms 2400 KB Ok
26 Correct 64 ms 2852 KB Ok
27 Correct 64 ms 2784 KB Ok
28 Correct 62 ms 2400 KB Ok
29 Correct 59 ms 4320 KB Ok
30 Correct 66 ms 2656 KB Ok
31 Correct 67 ms 2400 KB Ok
32 Correct 66 ms 2272 KB Ok
33 Correct 65 ms 2528 KB Ok
34 Correct 87 ms 8672 KB Ok
35 Correct 93 ms 8672 KB Ok
36 Correct 87 ms 8672 KB Ok
37 Correct 93 ms 8544 KB Ok
38 Correct 89 ms 8604 KB Ok
39 Correct 90 ms 8680 KB Ok
40 Correct 96 ms 8672 KB Ok
41 Correct 104 ms 8672 KB Ok
42 Correct 86 ms 8544 KB Ok
43 Correct 95 ms 8672 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2656 KB Ok
4 Correct 52 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 63 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 54 ms 5372 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 58 ms 2400 KB Ok
13 Correct 70 ms 8416 KB Ok
14 Correct 73 ms 8416 KB Ok
15 Correct 64 ms 8416 KB Ok
16 Correct 68 ms 8428 KB Ok
17 Correct 72 ms 8416 KB Ok
18 Correct 64 ms 8544 KB Ok
19 Correct 84 ms 8820 KB Ok
20 Correct 78 ms 8672 KB Ok
21 Correct 121 ms 8972 KB Ok
22 Correct 79 ms 8928 KB Ok
23 Correct 30 ms 8544 KB Ok
24 Correct 73 ms 8416 KB Ok
25 Correct 66 ms 8448 KB Ok
26 Correct 75 ms 8416 KB Ok
27 Correct 73 ms 8416 KB Ok
28 Correct 81 ms 8544 KB Ok
29 Correct 69 ms 8416 KB Ok
30 Correct 78 ms 8416 KB Ok
31 Correct 71 ms 8500 KB Ok
32 Correct 76 ms 8416 KB Ok
33 Correct 77 ms 8544 KB Ok
34 Correct 64 ms 2272 KB Ok
35 Correct 63 ms 2400 KB Ok
36 Correct 64 ms 2852 KB Ok
37 Correct 64 ms 2784 KB Ok
38 Correct 62 ms 2400 KB Ok
39 Correct 59 ms 4320 KB Ok
40 Correct 66 ms 2656 KB Ok
41 Correct 67 ms 2400 KB Ok
42 Correct 66 ms 2272 KB Ok
43 Correct 65 ms 2528 KB Ok
44 Correct 87 ms 8672 KB Ok
45 Correct 93 ms 8672 KB Ok
46 Correct 87 ms 8672 KB Ok
47 Correct 93 ms 8544 KB Ok
48 Correct 89 ms 8604 KB Ok
49 Correct 90 ms 8680 KB Ok
50 Correct 96 ms 8672 KB Ok
51 Correct 104 ms 8672 KB Ok
52 Correct 86 ms 8544 KB Ok
53 Correct 95 ms 8672 KB Ok
54 Correct 273 ms 3936 KB Ok
55 Correct 306 ms 4448 KB Ok
56 Correct 299 ms 4192 KB Ok
57 Correct 225 ms 3680 KB Ok
58 Correct 274 ms 3680 KB Ok
59 Correct 255 ms 3648 KB Ok
60 Correct 228 ms 3424 KB Ok
61 Correct 237 ms 3552 KB Ok
62 Correct 294 ms 3936 KB Ok
63 Correct 243 ms 3760 KB Ok
64 Correct 295 ms 4320 KB Ok
65 Correct 272 ms 3936 KB Ok
66 Correct 252 ms 3808 KB Ok
67 Correct 226 ms 3680 KB Ok
68 Correct 253 ms 3712 KB Ok
69 Correct 456 ms 14560 KB Ok
70 Correct 469 ms 15072 KB Ok
71 Correct 442 ms 14560 KB Ok
72 Correct 465 ms 14432 KB Ok
73 Correct 460 ms 14560 KB Ok
74 Correct 457 ms 14432 KB Ok
75 Correct 473 ms 13920 KB Ok
76 Correct 475 ms 14688 KB Ok
77 Correct 437 ms 14248 KB Ok
78 Correct 460 ms 14560 KB Ok
79 Correct 471 ms 14688 KB Ok
80 Correct 474 ms 14968 KB Ok
81 Correct 473 ms 14740 KB Ok
82 Correct 455 ms 14688 KB Ok
83 Correct 452 ms 14176 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2656 KB Ok
4 Correct 52 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 63 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 54 ms 5372 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 58 ms 2400 KB Ok
13 Correct 70 ms 8416 KB Ok
14 Correct 73 ms 8416 KB Ok
15 Correct 64 ms 8416 KB Ok
16 Correct 68 ms 8428 KB Ok
17 Correct 72 ms 8416 KB Ok
18 Correct 64 ms 8544 KB Ok
19 Correct 84 ms 8820 KB Ok
20 Correct 78 ms 8672 KB Ok
21 Correct 121 ms 8972 KB Ok
22 Correct 79 ms 8928 KB Ok
23 Correct 30 ms 8544 KB Ok
24 Correct 73 ms 8416 KB Ok
25 Correct 66 ms 8448 KB Ok
26 Correct 75 ms 8416 KB Ok
27 Correct 73 ms 8416 KB Ok
28 Correct 81 ms 8544 KB Ok
29 Correct 69 ms 8416 KB Ok
30 Correct 78 ms 8416 KB Ok
31 Correct 71 ms 8500 KB Ok
32 Correct 76 ms 8416 KB Ok
33 Correct 77 ms 8544 KB Ok
34 Correct 80 ms 8416 KB Ok
35 Correct 87 ms 8416 KB Ok
36 Correct 87 ms 8416 KB Ok
37 Correct 90 ms 8416 KB Ok
38 Correct 80 ms 8416 KB Ok
39 Correct 435 ms 11984 KB Ok
40 Correct 355 ms 10564 KB Ok
41 Correct 655 ms 14024 KB Ok
42 Correct 478 ms 13024 KB Ok
43 Correct 288 ms 9952 KB Ok
44 Correct 425 ms 12128 KB Ok
45 Correct 64 ms 2272 KB Ok
46 Correct 63 ms 2400 KB Ok
47 Correct 64 ms 2852 KB Ok
48 Correct 64 ms 2784 KB Ok
49 Correct 62 ms 2400 KB Ok
50 Correct 59 ms 4320 KB Ok
51 Correct 66 ms 2656 KB Ok
52 Correct 67 ms 2400 KB Ok
53 Correct 66 ms 2272 KB Ok
54 Correct 65 ms 2528 KB Ok
55 Correct 87 ms 8672 KB Ok
56 Correct 93 ms 8672 KB Ok
57 Correct 87 ms 8672 KB Ok
58 Correct 93 ms 8544 KB Ok
59 Correct 89 ms 8604 KB Ok
60 Correct 90 ms 8680 KB Ok
61 Correct 96 ms 8672 KB Ok
62 Correct 104 ms 8672 KB Ok
63 Correct 86 ms 8544 KB Ok
64 Correct 95 ms 8672 KB Ok
65 Correct 273 ms 3936 KB Ok
66 Correct 306 ms 4448 KB Ok
67 Correct 299 ms 4192 KB Ok
68 Correct 225 ms 3680 KB Ok
69 Correct 274 ms 3680 KB Ok
70 Correct 255 ms 3648 KB Ok
71 Correct 228 ms 3424 KB Ok
72 Correct 237 ms 3552 KB Ok
73 Correct 294 ms 3936 KB Ok
74 Correct 243 ms 3760 KB Ok
75 Correct 295 ms 4320 KB Ok
76 Correct 272 ms 3936 KB Ok
77 Correct 252 ms 3808 KB Ok
78 Correct 226 ms 3680 KB Ok
79 Correct 253 ms 3712 KB Ok
80 Correct 456 ms 14560 KB Ok
81 Correct 469 ms 15072 KB Ok
82 Correct 442 ms 14560 KB Ok
83 Correct 465 ms 14432 KB Ok
84 Correct 460 ms 14560 KB Ok
85 Correct 457 ms 14432 KB Ok
86 Correct 473 ms 13920 KB Ok
87 Correct 475 ms 14688 KB Ok
88 Correct 437 ms 14248 KB Ok
89 Correct 460 ms 14560 KB Ok
90 Correct 471 ms 14688 KB Ok
91 Correct 474 ms 14968 KB Ok
92 Correct 473 ms 14740 KB Ok
93 Correct 455 ms 14688 KB Ok
94 Correct 452 ms 14176 KB Ok
95 Correct 586 ms 7480 KB Ok
96 Correct 883 ms 9556 KB Ok
97 Correct 828 ms 8284 KB Ok
98 Correct 609 ms 7516 KB Ok
99 Correct 749 ms 7900 KB Ok
100 Correct 769 ms 8156 KB Ok
101 Correct 787 ms 8532 KB Ok
102 Correct 754 ms 8028 KB Ok
103 Correct 733 ms 8508 KB Ok
104 Correct 881 ms 9692 KB Ok
105 Correct 833 ms 9436 KB Ok
106 Correct 779 ms 9052 KB Ok
107 Correct 802 ms 8748 KB Ok
108 Correct 877 ms 9564 KB Ok
109 Correct 828 ms 9436 KB Ok
110 Correct 1893 ms 41692 KB Ok
111 Correct 1982 ms 44380 KB Ok
112 Correct 1914 ms 44216 KB Ok
113 Correct 1930 ms 43484 KB Ok
114 Correct 1889 ms 45404 KB Ok
115 Correct 1930 ms 43200 KB Ok
116 Correct 1938 ms 44828 KB Ok
117 Correct 1954 ms 43176 KB Ok
118 Correct 1831 ms 43252 KB Ok
119 Correct 1982 ms 43228 KB Ok
120 Correct 1897 ms 42844 KB Ok
121 Correct 1910 ms 41820 KB Ok
122 Correct 1940 ms 44124 KB Ok
123 Correct 1896 ms 44536 KB Ok
124 Correct 1884 ms 41948 KB Ok
125 Correct 1791 ms 26716 KB Ok