oj.uz

Submission #335337

# Submission time Handle Problem Language Result Execution time Memory
335337 2020-12-12T01:50:48 Z limabeans Nice sequence (IZhO18_sequence) C++17
100 / 100
 1954 ms 45676 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;





int n, m;

bool viz[maxn];
int p[maxn]; //p[i-m] < p[i] > p[i+n]
vector<int> topo;



void dfs(int i, int len) {
    assert(!viz[i]);
    viz[i]=true;
    if (i-m>=0 && !viz[i-m]) dfs(i-m,len);
    if (i+n<=len && !viz[i+n]) dfs(i+n,len);
    topo.push_back(i);
}

bool test(int len) {

    topo.clear();
    for (int i=0; i<=len; i++) {
	viz[i]=false;
	p[i]=0;
    }

    for (int i=0; i<=len; i++) {
	if (!viz[i]) dfs(i,len);
    }
    for (int i=0; i<=len; i++) {
	p[topo[i]]=i;
    }

    for (int i=0; i<=len; i++) {
	if (i-n>=0 && p[i]>=p[i-n]) return false;
	if (i+m<=len && p[i+m]<=p[i]) return false;
    }
    return true;
}

void solve() {
    cin>>n>>m;
    int lo=0;
    int hi=4e5+1;
    while (hi-lo>1) {
	int mid=(lo+hi)/2;
	if (test(mid)) {
	    lo=mid;
	} else {
	    hi=mid;
	}
    }

    test(lo);
    cout<<lo<<"\n";
    if (lo) {
	for (int i=1; i<=lo; i++) {
	    cout<<p[i]-p[i-1]<<" ";
	}
	cout<<"\n";
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    int t;
    cin>>t;
    while (t--) {
	solve();
    }	    
    
    
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8684 KB Ok
2 Correct 72 ms 8684 KB Ok
3 Correct 56 ms 2660 KB Ok
4 Correct 57 ms 3176 KB Ok
5 Correct 56 ms 2668 KB Ok
6 Correct 60 ms 3944 KB Ok
7 Correct 59 ms 2668 KB Ok
8 Correct 59 ms 4076 KB Ok
9 Correct 57 ms 2664 KB Ok
10 Correct 57 ms 5352 KB Ok
11 Correct 56 ms 2540 KB Ok
12 Correct 54 ms 2540 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8552 KB Ok
2 Correct 74 ms 8552 KB Ok
3 Correct 69 ms 8552 KB Ok
4 Correct 69 ms 8552 KB Ok
5 Correct 74 ms 8552 KB Ok
6 Correct 80 ms 8684 KB Ok
7 Correct 88 ms 8808 KB Ok
8 Correct 80 ms 8684 KB Ok
9 Correct 92 ms 8936 KB Ok
10 Correct 82 ms 8936 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8820 KB Ok
2 Correct 77 ms 8684 KB Ok
3 Correct 77 ms 8552 KB Ok
4 Correct 80 ms 8684 KB Ok
5 Correct 79 ms 8684 KB Ok
6 Correct 82 ms 8552 KB Ok
7 Correct 73 ms 8684 KB Ok
8 Correct 86 ms 8684 KB Ok
9 Correct 86 ms 8552 KB Ok
10 Correct 81 ms 8552 KB Ok
11 Correct 82 ms 8552 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 8684 KB Ok
2 Correct 87 ms 8684 KB Ok
3 Correct 87 ms 8684 KB Ok
4 Correct 92 ms 8684 KB Ok
5 Correct 86 ms 8684 KB Ok
6 Correct 378 ms 12008 KB Ok
7 Correct 344 ms 10728 KB Ok
8 Correct 644 ms 14184 KB Ok
9 Correct 452 ms 13032 KB Ok
10 Correct 283 ms 10088 KB Ok
11 Correct 411 ms 12008 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8684 KB Ok
2 Correct 72 ms 8684 KB Ok
3 Correct 56 ms 2660 KB Ok
4 Correct 57 ms 3176 KB Ok
5 Correct 56 ms 2668 KB Ok
6 Correct 60 ms 3944 KB Ok
7 Correct 59 ms 2668 KB Ok
8 Correct 59 ms 4076 KB Ok
9 Correct 57 ms 2664 KB Ok
10 Correct 57 ms 5352 KB Ok
11 Correct 56 ms 2540 KB Ok
12 Correct 54 ms 2540 KB Ok
13 Correct 33 ms 8820 KB Ok
14 Correct 77 ms 8684 KB Ok
15 Correct 77 ms 8552 KB Ok
16 Correct 80 ms 8684 KB Ok
17 Correct 79 ms 8684 KB Ok
18 Correct 82 ms 8552 KB Ok
19 Correct 73 ms 8684 KB Ok
20 Correct 86 ms 8684 KB Ok
21 Correct 86 ms 8552 KB Ok
22 Correct 81 ms 8552 KB Ok
23 Correct 82 ms 8552 KB Ok
24 Correct 69 ms 2540 KB Ok
25 Correct 66 ms 2444 KB Ok
26 Correct 68 ms 2924 KB Ok
27 Correct 67 ms 2792 KB Ok
28 Correct 67 ms 2540 KB Ok
29 Correct 64 ms 4328 KB Ok
30 Correct 71 ms 2924 KB Ok
31 Correct 70 ms 2540 KB Ok
32 Correct 69 ms 2540 KB Ok
33 Correct 73 ms 2664 KB Ok
34 Correct 90 ms 8680 KB Ok
35 Correct 93 ms 8684 KB Ok
36 Correct 92 ms 8684 KB Ok
37 Correct 95 ms 8684 KB Ok
38 Correct 93 ms 8680 KB Ok
39 Correct 91 ms 8680 KB Ok
40 Correct 94 ms 8684 KB Ok
41 Correct 95 ms 8684 KB Ok
42 Correct 91 ms 8812 KB Ok
43 Correct 97 ms 8724 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8684 KB Ok
2 Correct 72 ms 8684 KB Ok
3 Correct 56 ms 2660 KB Ok
4 Correct 57 ms 3176 KB Ok
5 Correct 56 ms 2668 KB Ok
6 Correct 60 ms 3944 KB Ok
7 Correct 59 ms 2668 KB Ok
8 Correct 59 ms 4076 KB Ok
9 Correct 57 ms 2664 KB Ok
10 Correct 57 ms 5352 KB Ok
11 Correct 56 ms 2540 KB Ok
12 Correct 54 ms 2540 KB Ok
13 Correct 74 ms 8552 KB Ok
14 Correct 74 ms 8552 KB Ok
15 Correct 69 ms 8552 KB Ok
16 Correct 69 ms 8552 KB Ok
17 Correct 74 ms 8552 KB Ok
18 Correct 80 ms 8684 KB Ok
19 Correct 88 ms 8808 KB Ok
20 Correct 80 ms 8684 KB Ok
21 Correct 92 ms 8936 KB Ok
22 Correct 82 ms 8936 KB Ok
23 Correct 33 ms 8820 KB Ok
24 Correct 77 ms 8684 KB Ok
25 Correct 77 ms 8552 KB Ok
26 Correct 80 ms 8684 KB Ok
27 Correct 79 ms 8684 KB Ok
28 Correct 82 ms 8552 KB Ok
29 Correct 73 ms 8684 KB Ok
30 Correct 86 ms 8684 KB Ok
31 Correct 86 ms 8552 KB Ok
32 Correct 81 ms 8552 KB Ok
33 Correct 82 ms 8552 KB Ok
34 Correct 69 ms 2540 KB Ok
35 Correct 66 ms 2444 KB Ok
36 Correct 68 ms 2924 KB Ok
37 Correct 67 ms 2792 KB Ok
38 Correct 67 ms 2540 KB Ok
39 Correct 64 ms 4328 KB Ok
40 Correct 71 ms 2924 KB Ok
41 Correct 70 ms 2540 KB Ok
42 Correct 69 ms 2540 KB Ok
43 Correct 73 ms 2664 KB Ok
44 Correct 90 ms 8680 KB Ok
45 Correct 93 ms 8684 KB Ok
46 Correct 92 ms 8684 KB Ok
47 Correct 95 ms 8684 KB Ok
48 Correct 93 ms 8680 KB Ok
49 Correct 91 ms 8680 KB Ok
50 Correct 94 ms 8684 KB Ok
51 Correct 95 ms 8684 KB Ok
52 Correct 91 ms 8812 KB Ok
53 Correct 97 ms 8724 KB Ok
54 Correct 264 ms 3944 KB Ok
55 Correct 303 ms 4328 KB Ok
56 Correct 298 ms 4200 KB Ok
57 Correct 223 ms 3560 KB Ok
58 Correct 268 ms 3816 KB Ok
59 Correct 250 ms 3688 KB Ok
60 Correct 224 ms 3560 KB Ok
61 Correct 232 ms 3560 KB Ok
62 Correct 293 ms 4268 KB Ok
63 Correct 242 ms 3688 KB Ok
64 Correct 287 ms 4328 KB Ok
65 Correct 272 ms 4072 KB Ok
66 Correct 249 ms 3752 KB Ok
67 Correct 218 ms 3688 KB Ok
68 Correct 252 ms 3944 KB Ok
69 Correct 457 ms 14696 KB Ok
70 Correct 474 ms 15080 KB Ok
71 Correct 448 ms 14696 KB Ok
72 Correct 463 ms 14568 KB Ok
73 Correct 445 ms 14696 KB Ok
74 Correct 447 ms 14440 KB Ok
75 Correct 462 ms 13928 KB Ok
76 Correct 477 ms 14696 KB Ok
77 Correct 434 ms 14056 KB Ok
78 Correct 458 ms 14568 KB Ok
79 Correct 462 ms 14696 KB Ok
80 Correct 457 ms 14824 KB Ok
81 Correct 460 ms 14696 KB Ok
82 Correct 450 ms 14568 KB Ok
83 Correct 446 ms 14312 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8684 KB Ok
2 Correct 72 ms 8684 KB Ok
3 Correct 56 ms 2660 KB Ok
4 Correct 57 ms 3176 KB Ok
5 Correct 56 ms 2668 KB Ok
6 Correct 60 ms 3944 KB Ok
7 Correct 59 ms 2668 KB Ok
8 Correct 59 ms 4076 KB Ok
9 Correct 57 ms 2664 KB Ok
10 Correct 57 ms 5352 KB Ok
11 Correct 56 ms 2540 KB Ok
12 Correct 54 ms 2540 KB Ok
13 Correct 74 ms 8552 KB Ok
14 Correct 74 ms 8552 KB Ok
15 Correct 69 ms 8552 KB Ok
16 Correct 69 ms 8552 KB Ok
17 Correct 74 ms 8552 KB Ok
18 Correct 80 ms 8684 KB Ok
19 Correct 88 ms 8808 KB Ok
20 Correct 80 ms 8684 KB Ok
21 Correct 92 ms 8936 KB Ok
22 Correct 82 ms 8936 KB Ok
23 Correct 33 ms 8820 KB Ok
24 Correct 77 ms 8684 KB Ok
25 Correct 77 ms 8552 KB Ok
26 Correct 80 ms 8684 KB Ok
27 Correct 79 ms 8684 KB Ok
28 Correct 82 ms 8552 KB Ok
29 Correct 73 ms 8684 KB Ok
30 Correct 86 ms 8684 KB Ok
31 Correct 86 ms 8552 KB Ok
32 Correct 81 ms 8552 KB Ok
33 Correct 82 ms 8552 KB Ok
34 Correct 84 ms 8684 KB Ok
35 Correct 87 ms 8684 KB Ok
36 Correct 87 ms 8684 KB Ok
37 Correct 92 ms 8684 KB Ok
38 Correct 86 ms 8684 KB Ok
39 Correct 378 ms 12008 KB Ok
40 Correct 344 ms 10728 KB Ok
41 Correct 644 ms 14184 KB Ok
42 Correct 452 ms 13032 KB Ok
43 Correct 283 ms 10088 KB Ok
44 Correct 411 ms 12008 KB Ok
45 Correct 69 ms 2540 KB Ok
46 Correct 66 ms 2444 KB Ok
47 Correct 68 ms 2924 KB Ok
48 Correct 67 ms 2792 KB Ok
49 Correct 67 ms 2540 KB Ok
50 Correct 64 ms 4328 KB Ok
51 Correct 71 ms 2924 KB Ok
52 Correct 70 ms 2540 KB Ok
53 Correct 69 ms 2540 KB Ok
54 Correct 73 ms 2664 KB Ok
55 Correct 90 ms 8680 KB Ok
56 Correct 93 ms 8684 KB Ok
57 Correct 92 ms 8684 KB Ok
58 Correct 95 ms 8684 KB Ok
59 Correct 93 ms 8680 KB Ok
60 Correct 91 ms 8680 KB Ok
61 Correct 94 ms 8684 KB Ok
62 Correct 95 ms 8684 KB Ok
63 Correct 91 ms 8812 KB Ok
64 Correct 97 ms 8724 KB Ok
65 Correct 264 ms 3944 KB Ok
66 Correct 303 ms 4328 KB Ok
67 Correct 298 ms 4200 KB Ok
68 Correct 223 ms 3560 KB Ok
69 Correct 268 ms 3816 KB Ok
70 Correct 250 ms 3688 KB Ok
71 Correct 224 ms 3560 KB Ok
72 Correct 232 ms 3560 KB Ok
73 Correct 293 ms 4268 KB Ok
74 Correct 242 ms 3688 KB Ok
75 Correct 287 ms 4328 KB Ok
76 Correct 272 ms 4072 KB Ok
77 Correct 249 ms 3752 KB Ok
78 Correct 218 ms 3688 KB Ok
79 Correct 252 ms 3944 KB Ok
80 Correct 457 ms 14696 KB Ok
81 Correct 474 ms 15080 KB Ok
82 Correct 448 ms 14696 KB Ok
83 Correct 463 ms 14568 KB Ok
84 Correct 445 ms 14696 KB Ok
85 Correct 447 ms 14440 KB Ok
86 Correct 462 ms 13928 KB Ok
87 Correct 477 ms 14696 KB Ok
88 Correct 434 ms 14056 KB Ok
89 Correct 458 ms 14568 KB Ok
90 Correct 462 ms 14696 KB Ok
91 Correct 457 ms 14824 KB Ok
92 Correct 460 ms 14696 KB Ok
93 Correct 450 ms 14568 KB Ok
94 Correct 446 ms 14312 KB Ok
95 Correct 574 ms 7780 KB Ok
96 Correct 862 ms 9500 KB Ok
97 Correct 823 ms 8420 KB Ok
98 Correct 602 ms 7524 KB Ok
99 Correct 744 ms 7908 KB Ok
100 Correct 751 ms 8072 KB Ok
101 Correct 771 ms 8676 KB Ok
102 Correct 746 ms 8164 KB Ok
103 Correct 720 ms 8548 KB Ok
104 Correct 866 ms 9572 KB Ok
105 Correct 829 ms 9316 KB Ok
106 Correct 725 ms 9188 KB Ok
107 Correct 788 ms 8932 KB Ok
108 Correct 860 ms 9444 KB Ok
109 Correct 796 ms 9572 KB Ok
110 Correct 1862 ms 41684 KB Ok
111 Correct 1914 ms 44332 KB Ok
112 Correct 1886 ms 44148 KB Ok
113 Correct 1919 ms 43492 KB Ok
114 Correct 1883 ms 45676 KB Ok
115 Correct 1934 ms 43364 KB Ok
116 Correct 1923 ms 44516 KB Ok
117 Correct 1940 ms 43108 KB Ok
118 Correct 1822 ms 43372 KB Ok
119 Correct 1954 ms 43108 KB Ok
120 Correct 1885 ms 42852 KB Ok
121 Correct 1886 ms 41444 KB Ok
122 Correct 1908 ms 44016 KB Ok
123 Correct 1930 ms 44480 KB Ok
124 Correct 1875 ms 41856 KB Ok
125 Correct 1777 ms 26764 KB Ok