oj.uz

Submission #334936

# Submission time Handle Problem Language Result Execution time Memory
334936 2020-12-10T10:56:41 Z beksultan04 Nice sequence (IZhO18_sequence) C++14
100 / 100
 1841 ms 46816 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%lld",&a);
#define scan2(a,b) scanf("%lld %lld",&a, &b);
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define pb push_back
#define endi puts("");
const int N = 5e5+12,INF=1e9+7;
int sz,vis[N],pref[N],m,n;
vector <int> v;
void dfs(int x){
    vis[x]=1;
    if (x-m >= 0 && !vis[x-m]){
        dfs(x-m);
    }
    if (x+n<=sz && !vis[x+n]){
        dfs(x+n);
    }
    v.pb(x);
}

bool is(int x){
    sz = x;
    v.clear();
    int i;
    for (i=0;i<=sz;++i)
        vis[i]=0;
    for (i=0;i<=sz;++i)
        if (!vis[i])dfs(i);
    for (i=0;i<v.size();++i){
        pref[v[i]]=i;
    }
    for (i=0;i<=sz;++i){
        if (i-m >= 0 && pref[i] <= pref[i-m])ret 0;
        if (i+n <= sz && pref[i] <= pref[i+n])ret 0;
    }
    ret 1;
}

main(){
    ios_base::sync_with_stdio(NULL);
    int t;
    cin>>t;
    while (t--){
        int i,j;
        cin>>n>>m;
        int l=0,r=n+m;
        while (l<r){
            int m = (l+r+1)>>1;
            if (is(m)){
                l=m;
            }
            else r = m-1;
        }
        is(l);
        cout <<l<<"\n";
        for (i=1;i<=l;++i){
            cout <<pref[i]-pref[i-1]<<" ";
        }
        endi
    }
}

Compilation message

sequence.cpp: In function 'bool is(int)':
sequence.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (i=0;i<v.size();++i){
      |              ~^~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      |      ^
sequence.cpp: In function 'int main()':
sequence.cpp:52:15: warning: unused variable 'j' [-Wunused-variable]
   52 |         int i,j;
      |               ^

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 4 ms 492 KB Ok
7 Correct 22 ms 1260 KB Ok
8 Correct 10 ms 748 KB Ok
9 Correct 26 ms 1260 KB Ok
10 Correct 15 ms 876 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 283 ms 10684 KB Ok
7 Correct 260 ms 11236 KB Ok
8 Correct 529 ms 14052 KB Ok
9 Correct 361 ms 12516 KB Ok
10 Correct 194 ms 6380 KB Ok
11 Correct 301 ms 12520 KB Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 4 ms 492 KB Ok
19 Correct 22 ms 1260 KB Ok
20 Correct 10 ms 748 KB Ok
21 Correct 26 ms 1260 KB Ok
22 Correct 15 ms 876 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 5 ms 492 KB Ok
35 Correct 5 ms 492 KB Ok
36 Correct 5 ms 492 KB Ok
37 Correct 4 ms 492 KB Ok
38 Correct 4 ms 492 KB Ok
39 Correct 4 ms 492 KB Ok
40 Correct 4 ms 364 KB Ok
41 Correct 4 ms 492 KB Ok
42 Correct 5 ms 492 KB Ok
43 Correct 4 ms 492 KB Ok
44 Correct 10 ms 620 KB Ok
45 Correct 10 ms 620 KB Ok
46 Correct 10 ms 620 KB Ok
47 Correct 11 ms 620 KB Ok
48 Correct 9 ms 620 KB Ok
49 Correct 9 ms 620 KB Ok
50 Correct 11 ms 620 KB Ok
51 Correct 10 ms 620 KB Ok
52 Correct 10 ms 620 KB Ok
53 Correct 10 ms 620 KB Ok
54 Correct 215 ms 3304 KB Ok
55 Correct 242 ms 3560 KB Ok
56 Correct 238 ms 3704 KB Ok
57 Correct 175 ms 2792 KB Ok
58 Correct 206 ms 3048 KB Ok
59 Correct 196 ms 2920 KB Ok
60 Correct 175 ms 2664 KB Ok
61 Correct 182 ms 2920 KB Ok
62 Correct 245 ms 3432 KB Ok
63 Correct 193 ms 2920 KB Ok
64 Correct 241 ms 3688 KB Ok
65 Correct 218 ms 3304 KB Ok
66 Correct 197 ms 3048 KB Ok
67 Correct 190 ms 2920 KB Ok
68 Correct 208 ms 3048 KB Ok
69 Correct 399 ms 10728 KB Ok
70 Correct 432 ms 11368 KB Ok
71 Correct 385 ms 10796 KB Ok
72 Correct 388 ms 10728 KB Ok
73 Correct 384 ms 10856 KB Ok
74 Correct 374 ms 10600 KB Ok
75 Correct 401 ms 10216 KB Ok
76 Correct 397 ms 10984 KB Ok
77 Correct 379 ms 10344 KB Ok
78 Correct 381 ms 10728 KB Ok
79 Correct 388 ms 10984 KB Ok
80 Correct 379 ms 10984 KB Ok
81 Correct 393 ms 11060 KB Ok
82 Correct 380 ms 11112 KB Ok
83 Correct 398 ms 10316 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 4 ms 492 KB Ok
19 Correct 22 ms 1260 KB Ok
20 Correct 10 ms 748 KB Ok
21 Correct 26 ms 1260 KB Ok
22 Correct 15 ms 876 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 1 ms 364 KB Ok
39 Correct 283 ms 10684 KB Ok
40 Correct 260 ms 11236 KB Ok
41 Correct 529 ms 14052 KB Ok
42 Correct 361 ms 12516 KB Ok
43 Correct 194 ms 6380 KB Ok
44 Correct 301 ms 12520 KB Ok
45 Correct 5 ms 492 KB Ok
46 Correct 5 ms 492 KB Ok
47 Correct 5 ms 492 KB Ok
48 Correct 4 ms 492 KB Ok
49 Correct 4 ms 492 KB Ok
50 Correct 4 ms 492 KB Ok
51 Correct 4 ms 364 KB Ok
52 Correct 4 ms 492 KB Ok
53 Correct 5 ms 492 KB Ok
54 Correct 4 ms 492 KB Ok
55 Correct 10 ms 620 KB Ok
56 Correct 10 ms 620 KB Ok
57 Correct 10 ms 620 KB Ok
58 Correct 11 ms 620 KB Ok
59 Correct 9 ms 620 KB Ok
60 Correct 9 ms 620 KB Ok
61 Correct 11 ms 620 KB Ok
62 Correct 10 ms 620 KB Ok
63 Correct 10 ms 620 KB Ok
64 Correct 10 ms 620 KB Ok
65 Correct 215 ms 3304 KB Ok
66 Correct 242 ms 3560 KB Ok
67 Correct 238 ms 3704 KB Ok
68 Correct 175 ms 2792 KB Ok
69 Correct 206 ms 3048 KB Ok
70 Correct 196 ms 2920 KB Ok
71 Correct 175 ms 2664 KB Ok
72 Correct 182 ms 2920 KB Ok
73 Correct 245 ms 3432 KB Ok
74 Correct 193 ms 2920 KB Ok
75 Correct 241 ms 3688 KB Ok
76 Correct 218 ms 3304 KB Ok
77 Correct 197 ms 3048 KB Ok
78 Correct 190 ms 2920 KB Ok
79 Correct 208 ms 3048 KB Ok
80 Correct 399 ms 10728 KB Ok
81 Correct 432 ms 11368 KB Ok
82 Correct 385 ms 10796 KB Ok
83 Correct 388 ms 10728 KB Ok
84 Correct 384 ms 10856 KB Ok
85 Correct 374 ms 10600 KB Ok
86 Correct 401 ms 10216 KB Ok
87 Correct 397 ms 10984 KB Ok
88 Correct 379 ms 10344 KB Ok
89 Correct 381 ms 10728 KB Ok
90 Correct 388 ms 10984 KB Ok
91 Correct 379 ms 10984 KB Ok
92 Correct 393 ms 11060 KB Ok
93 Correct 380 ms 11112 KB Ok
94 Correct 398 ms 10316 KB Ok
95 Correct 544 ms 7680 KB Ok
96 Correct 815 ms 10336 KB Ok
97 Correct 758 ms 9064 KB Ok
98 Correct 578 ms 8160 KB Ok
99 Correct 696 ms 8544 KB Ok
100 Correct 677 ms 8544 KB Ok
101 Correct 715 ms 9440 KB Ok
102 Correct 689 ms 8800 KB Ok
103 Correct 681 ms 9184 KB Ok
104 Correct 837 ms 10720 KB Ok
105 Correct 760 ms 10208 KB Ok
106 Correct 677 ms 10080 KB Ok
107 Correct 760 ms 9824 KB Ok
108 Correct 818 ms 10460 KB Ok
109 Correct 747 ms 10592 KB Ok
110 Correct 1805 ms 42660 KB Ok
111 Correct 1811 ms 45512 KB Ok
112 Correct 1834 ms 45436 KB Ok
113 Correct 1796 ms 44600 KB Ok
114 Correct 1793 ms 46816 KB Ok
115 Correct 1821 ms 44384 KB Ok
116 Correct 1830 ms 45792 KB Ok
117 Correct 1787 ms 44384 KB Ok
118 Correct 1749 ms 44512 KB Ok
119 Correct 1809 ms 44512 KB Ok
120 Correct 1765 ms 44384 KB Ok
121 Correct 1782 ms 42832 KB Ok
122 Correct 1760 ms 45536 KB Ok
123 Correct 1761 ms 45664 KB Ok
124 Correct 1841 ms 43104 KB Ok
125 Correct 1728 ms 27940 KB Ok