oj.uz

Submission #335336

# Submission time Handle Problem Language Result Execution time Memory
335336 2020-12-12T01:48:53 Z limabeans Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 41912 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=5e5;
    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 104 ms 10604 KB Ok
2 Correct 101 ms 10604 KB Ok
3 Correct 72 ms 3304 KB Ok
4 Correct 71 ms 3816 KB Ok
5 Correct 70 ms 3176 KB Ok
6 Correct 76 ms 4712 KB Ok
7 Correct 73 ms 3048 KB Ok
8 Correct 71 ms 4716 KB Ok
9 Correct 71 ms 3176 KB Ok
10 Correct 74 ms 6632 KB Ok
11 Correct 71 ms 3048 KB Ok
12 Correct 69 ms 2920 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 10472 KB Ok
2 Correct 101 ms 10472 KB Ok
3 Correct 92 ms 10648 KB Ok
4 Correct 88 ms 10472 KB Ok
5 Correct 90 ms 10472 KB Ok
6 Correct 92 ms 10600 KB Ok
7 Correct 102 ms 10856 KB Ok
8 Correct 101 ms 10728 KB Ok
9 Correct 108 ms 10984 KB Ok
10 Correct 99 ms 10728 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10604 KB Ok
2 Correct 107 ms 10624 KB Ok
3 Correct 96 ms 10472 KB Ok
4 Correct 102 ms 10604 KB Ok
5 Correct 103 ms 10604 KB Ok
6 Correct 106 ms 10472 KB Ok
7 Correct 92 ms 10604 KB Ok
8 Correct 101 ms 10604 KB Ok
9 Correct 96 ms 10472 KB Ok
10 Correct 99 ms 10472 KB Ok
11 Correct 105 ms 10600 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 10604 KB Ok
2 Correct 116 ms 10604 KB Ok
3 Correct 114 ms 10604 KB Ok
4 Correct 118 ms 10604 KB Ok
5 Correct 110 ms 10604 KB Ok
6 Correct 394 ms 14056 KB Ok
7 Correct 387 ms 12648 KB Ok
8 Correct 658 ms 15988 KB Ok
9 Correct 488 ms 15080 KB Ok
10 Correct 313 ms 11880 KB Ok
11 Correct 453 ms 14056 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10604 KB Ok
2 Correct 101 ms 10604 KB Ok
3 Correct 72 ms 3304 KB Ok
4 Correct 71 ms 3816 KB Ok
5 Correct 70 ms 3176 KB Ok
6 Correct 76 ms 4712 KB Ok
7 Correct 73 ms 3048 KB Ok
8 Correct 71 ms 4716 KB Ok
9 Correct 71 ms 3176 KB Ok
10 Correct 74 ms 6632 KB Ok
11 Correct 71 ms 3048 KB Ok
12 Correct 69 ms 2920 KB Ok
13 Correct 37 ms 10604 KB Ok
14 Correct 107 ms 10624 KB Ok
15 Correct 96 ms 10472 KB Ok
16 Correct 102 ms 10604 KB Ok
17 Correct 103 ms 10604 KB Ok
18 Correct 106 ms 10472 KB Ok
19 Correct 92 ms 10604 KB Ok
20 Correct 101 ms 10604 KB Ok
21 Correct 96 ms 10472 KB Ok
22 Correct 99 ms 10472 KB Ok
23 Correct 105 ms 10600 KB Ok
24 Correct 87 ms 2796 KB Ok
25 Correct 82 ms 3048 KB Ok
26 Correct 87 ms 3308 KB Ok
27 Correct 96 ms 3304 KB Ok
28 Correct 96 ms 2920 KB Ok
29 Correct 78 ms 5352 KB Ok
30 Correct 87 ms 3108 KB Ok
31 Correct 88 ms 2796 KB Ok
32 Correct 84 ms 2796 KB Ok
33 Correct 86 ms 3176 KB Ok
34 Correct 112 ms 10600 KB Ok
35 Correct 121 ms 10604 KB Ok
36 Correct 115 ms 10600 KB Ok
37 Correct 122 ms 10776 KB Ok
38 Correct 114 ms 10568 KB Ok
39 Correct 109 ms 10600 KB Ok
40 Correct 123 ms 10600 KB Ok
41 Correct 114 ms 10600 KB Ok
42 Correct 115 ms 10588 KB Ok
43 Correct 117 ms 10600 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10604 KB Ok
2 Correct 101 ms 10604 KB Ok
3 Correct 72 ms 3304 KB Ok
4 Correct 71 ms 3816 KB Ok
5 Correct 70 ms 3176 KB Ok
6 Correct 76 ms 4712 KB Ok
7 Correct 73 ms 3048 KB Ok
8 Correct 71 ms 4716 KB Ok
9 Correct 71 ms 3176 KB Ok
10 Correct 74 ms 6632 KB Ok
11 Correct 71 ms 3048 KB Ok
12 Correct 69 ms 2920 KB Ok
13 Correct 96 ms 10472 KB Ok
14 Correct 101 ms 10472 KB Ok
15 Correct 92 ms 10648 KB Ok
16 Correct 88 ms 10472 KB Ok
17 Correct 90 ms 10472 KB Ok
18 Correct 92 ms 10600 KB Ok
19 Correct 102 ms 10856 KB Ok
20 Correct 101 ms 10728 KB Ok
21 Correct 108 ms 10984 KB Ok
22 Correct 99 ms 10728 KB Ok
23 Correct 37 ms 10604 KB Ok
24 Correct 107 ms 10624 KB Ok
25 Correct 96 ms 10472 KB Ok
26 Correct 102 ms 10604 KB Ok
27 Correct 103 ms 10604 KB Ok
28 Correct 106 ms 10472 KB Ok
29 Correct 92 ms 10604 KB Ok
30 Correct 101 ms 10604 KB Ok
31 Correct 96 ms 10472 KB Ok
32 Correct 99 ms 10472 KB Ok
33 Correct 105 ms 10600 KB Ok
34 Correct 87 ms 2796 KB Ok
35 Correct 82 ms 3048 KB Ok
36 Correct 87 ms 3308 KB Ok
37 Correct 96 ms 3304 KB Ok
38 Correct 96 ms 2920 KB Ok
39 Correct 78 ms 5352 KB Ok
40 Correct 87 ms 3108 KB Ok
41 Correct 88 ms 2796 KB Ok
42 Correct 84 ms 2796 KB Ok
43 Correct 86 ms 3176 KB Ok
44 Correct 112 ms 10600 KB Ok
45 Correct 121 ms 10604 KB Ok
46 Correct 115 ms 10600 KB Ok
47 Correct 122 ms 10776 KB Ok
48 Correct 114 ms 10568 KB Ok
49 Correct 109 ms 10600 KB Ok
50 Correct 123 ms 10600 KB Ok
51 Correct 114 ms 10600 KB Ok
52 Correct 115 ms 10588 KB Ok
53 Correct 117 ms 10600 KB Ok
54 Correct 283 ms 4456 KB Ok
55 Correct 319 ms 4712 KB Ok
56 Correct 311 ms 4712 KB Ok
57 Correct 239 ms 4208 KB Ok
58 Correct 279 ms 4200 KB Ok
59 Correct 266 ms 4200 KB Ok
60 Correct 237 ms 4072 KB Ok
61 Correct 245 ms 4200 KB Ok
62 Correct 305 ms 4456 KB Ok
63 Correct 266 ms 4200 KB Ok
64 Correct 310 ms 4712 KB Ok
65 Correct 290 ms 4328 KB Ok
66 Correct 266 ms 4360 KB Ok
67 Correct 240 ms 4324 KB Ok
68 Correct 269 ms 4328 KB Ok
69 Correct 493 ms 14952 KB Ok
70 Correct 500 ms 15592 KB Ok
71 Correct 488 ms 14952 KB Ok
72 Correct 497 ms 15152 KB Ok
73 Correct 484 ms 15080 KB Ok
74 Correct 481 ms 14800 KB Ok
75 Correct 492 ms 14568 KB Ok
76 Correct 505 ms 15368 KB Ok
77 Correct 474 ms 14696 KB Ok
78 Correct 503 ms 14908 KB Ok
79 Correct 499 ms 15080 KB Ok
80 Correct 491 ms 15208 KB Ok
81 Correct 498 ms 15336 KB Ok
82 Correct 492 ms 15080 KB Ok
83 Correct 480 ms 14696 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10604 KB Ok
2 Correct 101 ms 10604 KB Ok
3 Correct 72 ms 3304 KB Ok
4 Correct 71 ms 3816 KB Ok
5 Correct 70 ms 3176 KB Ok
6 Correct 76 ms 4712 KB Ok
7 Correct 73 ms 3048 KB Ok
8 Correct 71 ms 4716 KB Ok
9 Correct 71 ms 3176 KB Ok
10 Correct 74 ms 6632 KB Ok
11 Correct 71 ms 3048 KB Ok
12 Correct 69 ms 2920 KB Ok
13 Correct 96 ms 10472 KB Ok
14 Correct 101 ms 10472 KB Ok
15 Correct 92 ms 10648 KB Ok
16 Correct 88 ms 10472 KB Ok
17 Correct 90 ms 10472 KB Ok
18 Correct 92 ms 10600 KB Ok
19 Correct 102 ms 10856 KB Ok
20 Correct 101 ms 10728 KB Ok
21 Correct 108 ms 10984 KB Ok
22 Correct 99 ms 10728 KB Ok
23 Correct 37 ms 10604 KB Ok
24 Correct 107 ms 10624 KB Ok
25 Correct 96 ms 10472 KB Ok
26 Correct 102 ms 10604 KB Ok
27 Correct 103 ms 10604 KB Ok
28 Correct 106 ms 10472 KB Ok
29 Correct 92 ms 10604 KB Ok
30 Correct 101 ms 10604 KB Ok
31 Correct 96 ms 10472 KB Ok
32 Correct 99 ms 10472 KB Ok
33 Correct 105 ms 10600 KB Ok
34 Correct 105 ms 10604 KB Ok
35 Correct 116 ms 10604 KB Ok
36 Correct 114 ms 10604 KB Ok
37 Correct 118 ms 10604 KB Ok
38 Correct 110 ms 10604 KB Ok
39 Correct 394 ms 14056 KB Ok
40 Correct 387 ms 12648 KB Ok
41 Correct 658 ms 15988 KB Ok
42 Correct 488 ms 15080 KB Ok
43 Correct 313 ms 11880 KB Ok
44 Correct 453 ms 14056 KB Ok
45 Correct 87 ms 2796 KB Ok
46 Correct 82 ms 3048 KB Ok
47 Correct 87 ms 3308 KB Ok
48 Correct 96 ms 3304 KB Ok
49 Correct 96 ms 2920 KB Ok
50 Correct 78 ms 5352 KB Ok
51 Correct 87 ms 3108 KB Ok
52 Correct 88 ms 2796 KB Ok
53 Correct 84 ms 2796 KB Ok
54 Correct 86 ms 3176 KB Ok
55 Correct 112 ms 10600 KB Ok
56 Correct 121 ms 10604 KB Ok
57 Correct 115 ms 10600 KB Ok
58 Correct 122 ms 10776 KB Ok
59 Correct 114 ms 10568 KB Ok
60 Correct 109 ms 10600 KB Ok
61 Correct 123 ms 10600 KB Ok
62 Correct 114 ms 10600 KB Ok
63 Correct 115 ms 10588 KB Ok
64 Correct 117 ms 10600 KB Ok
65 Correct 283 ms 4456 KB Ok
66 Correct 319 ms 4712 KB Ok
67 Correct 311 ms 4712 KB Ok
68 Correct 239 ms 4208 KB Ok
69 Correct 279 ms 4200 KB Ok
70 Correct 266 ms 4200 KB Ok
71 Correct 237 ms 4072 KB Ok
72 Correct 245 ms 4200 KB Ok
73 Correct 305 ms 4456 KB Ok
74 Correct 266 ms 4200 KB Ok
75 Correct 310 ms 4712 KB Ok
76 Correct 290 ms 4328 KB Ok
77 Correct 266 ms 4360 KB Ok
78 Correct 240 ms 4324 KB Ok
79 Correct 269 ms 4328 KB Ok
80 Correct 493 ms 14952 KB Ok
81 Correct 500 ms 15592 KB Ok
82 Correct 488 ms 14952 KB Ok
83 Correct 497 ms 15152 KB Ok
84 Correct 484 ms 15080 KB Ok
85 Correct 481 ms 14800 KB Ok
86 Correct 492 ms 14568 KB Ok
87 Correct 505 ms 15368 KB Ok
88 Correct 474 ms 14696 KB Ok
89 Correct 503 ms 14908 KB Ok
90 Correct 499 ms 15080 KB Ok
91 Correct 491 ms 15208 KB Ok
92 Correct 498 ms 15336 KB Ok
93 Correct 492 ms 15080 KB Ok
94 Correct 480 ms 14696 KB Ok
95 Correct 586 ms 7144 KB Ok
96 Correct 869 ms 9612 KB Ok
97 Correct 822 ms 9188 KB Ok
98 Correct 617 ms 7888 KB Ok
99 Correct 749 ms 8680 KB Ok
100 Correct 757 ms 8768 KB Ok
101 Correct 784 ms 8804 KB Ok
102 Correct 768 ms 8788 KB Ok
103 Correct 745 ms 8812 KB Ok
104 Correct 895 ms 10056 KB Ok
105 Correct 845 ms 9572 KB Ok
106 Correct 737 ms 8932 KB Ok
107 Correct 815 ms 9060 KB Ok
108 Correct 889 ms 9828 KB Ok
109 Correct 818 ms 10212 KB Ok
110 Correct 1981 ms 41828 KB Ok
111 Execution timed out 2041 ms 41912 KB Time limit exceeded
112 Halted 0 ms 0 KB -