oj.uz

Submission #334933

# Submission time Handle Problem Language Result Execution time Memory
334933 2020-12-10T10:39:13 Z beksultan04 Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 46932 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=400000;
        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 74 ms 9064 KB Ok
2 Correct 75 ms 9064 KB Ok
3 Correct 55 ms 3300 KB Ok
4 Correct 54 ms 3684 KB Ok
5 Correct 53 ms 3432 KB Ok
6 Correct 58 ms 4328 KB Ok
7 Correct 55 ms 3176 KB Ok
8 Correct 55 ms 4468 KB Ok
9 Correct 55 ms 3300 KB Ok
10 Correct 55 ms 5988 KB Ok
11 Correct 53 ms 3176 KB Ok
12 Correct 52 ms 3048 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 9064 KB Ok
2 Correct 68 ms 9064 KB Ok
3 Correct 67 ms 9064 KB Ok
4 Correct 70 ms 9064 KB Ok
5 Correct 70 ms 9064 KB Ok
6 Correct 68 ms 9188 KB Ok
7 Correct 85 ms 9444 KB Ok
8 Correct 75 ms 9236 KB Ok
9 Correct 91 ms 9572 KB Ok
10 Correct 80 ms 9316 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9064 KB Ok
2 Correct 73 ms 9064 KB Ok
3 Correct 72 ms 9064 KB Ok
4 Correct 74 ms 9064 KB Ok
5 Correct 71 ms 9064 KB Ok
6 Correct 81 ms 9064 KB Ok
7 Correct 70 ms 9064 KB Ok
8 Correct 83 ms 9064 KB Ok
9 Correct 75 ms 9060 KB Ok
10 Correct 76 ms 9064 KB Ok
11 Correct 76 ms 9064 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 9064 KB Ok
2 Correct 90 ms 9064 KB Ok
3 Correct 83 ms 9064 KB Ok
4 Correct 86 ms 9064 KB Ok
5 Correct 88 ms 9064 KB Ok
6 Correct 369 ms 12644 KB Ok
7 Correct 352 ms 11364 KB Ok
8 Correct 617 ms 14692 KB Ok
9 Correct 456 ms 13668 KB Ok
10 Correct 280 ms 10468 KB Ok
11 Correct 406 ms 12644 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 9064 KB Ok
2 Correct 75 ms 9064 KB Ok
3 Correct 55 ms 3300 KB Ok
4 Correct 54 ms 3684 KB Ok
5 Correct 53 ms 3432 KB Ok
6 Correct 58 ms 4328 KB Ok
7 Correct 55 ms 3176 KB Ok
8 Correct 55 ms 4468 KB Ok
9 Correct 55 ms 3300 KB Ok
10 Correct 55 ms 5988 KB Ok
11 Correct 53 ms 3176 KB Ok
12 Correct 52 ms 3048 KB Ok
13 Correct 36 ms 9064 KB Ok
14 Correct 73 ms 9064 KB Ok
15 Correct 72 ms 9064 KB Ok
16 Correct 74 ms 9064 KB Ok
17 Correct 71 ms 9064 KB Ok
18 Correct 81 ms 9064 KB Ok
19 Correct 70 ms 9064 KB Ok
20 Correct 83 ms 9064 KB Ok
21 Correct 75 ms 9060 KB Ok
22 Correct 76 ms 9064 KB Ok
23 Correct 76 ms 9064 KB Ok
24 Correct 66 ms 2920 KB Ok
25 Correct 65 ms 3044 KB Ok
26 Correct 66 ms 3304 KB Ok
27 Correct 65 ms 3428 KB Ok
28 Correct 63 ms 2920 KB Ok
29 Correct 60 ms 4964 KB Ok
30 Correct 68 ms 3176 KB Ok
31 Correct 66 ms 2920 KB Ok
32 Correct 65 ms 3048 KB Ok
33 Correct 65 ms 3428 KB Ok
34 Correct 94 ms 9316 KB Ok
35 Correct 94 ms 9188 KB Ok
36 Correct 90 ms 9316 KB Ok
37 Correct 94 ms 9188 KB Ok
38 Correct 96 ms 9188 KB Ok
39 Correct 94 ms 9188 KB Ok
40 Correct 100 ms 9188 KB Ok
41 Correct 95 ms 9336 KB Ok
42 Correct 91 ms 9192 KB Ok
43 Correct 109 ms 9188 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 9064 KB Ok
2 Correct 75 ms 9064 KB Ok
3 Correct 55 ms 3300 KB Ok
4 Correct 54 ms 3684 KB Ok
5 Correct 53 ms 3432 KB Ok
6 Correct 58 ms 4328 KB Ok
7 Correct 55 ms 3176 KB Ok
8 Correct 55 ms 4468 KB Ok
9 Correct 55 ms 3300 KB Ok
10 Correct 55 ms 5988 KB Ok
11 Correct 53 ms 3176 KB Ok
12 Correct 52 ms 3048 KB Ok
13 Correct 76 ms 9064 KB Ok
14 Correct 68 ms 9064 KB Ok
15 Correct 67 ms 9064 KB Ok
16 Correct 70 ms 9064 KB Ok
17 Correct 70 ms 9064 KB Ok
18 Correct 68 ms 9188 KB Ok
19 Correct 85 ms 9444 KB Ok
20 Correct 75 ms 9236 KB Ok
21 Correct 91 ms 9572 KB Ok
22 Correct 80 ms 9316 KB Ok
23 Correct 36 ms 9064 KB Ok
24 Correct 73 ms 9064 KB Ok
25 Correct 72 ms 9064 KB Ok
26 Correct 74 ms 9064 KB Ok
27 Correct 71 ms 9064 KB Ok
28 Correct 81 ms 9064 KB Ok
29 Correct 70 ms 9064 KB Ok
30 Correct 83 ms 9064 KB Ok
31 Correct 75 ms 9060 KB Ok
32 Correct 76 ms 9064 KB Ok
33 Correct 76 ms 9064 KB Ok
34 Correct 66 ms 2920 KB Ok
35 Correct 65 ms 3044 KB Ok
36 Correct 66 ms 3304 KB Ok
37 Correct 65 ms 3428 KB Ok
38 Correct 63 ms 2920 KB Ok
39 Correct 60 ms 4964 KB Ok
40 Correct 68 ms 3176 KB Ok
41 Correct 66 ms 2920 KB Ok
42 Correct 65 ms 3048 KB Ok
43 Correct 65 ms 3428 KB Ok
44 Correct 94 ms 9316 KB Ok
45 Correct 94 ms 9188 KB Ok
46 Correct 90 ms 9316 KB Ok
47 Correct 94 ms 9188 KB Ok
48 Correct 96 ms 9188 KB Ok
49 Correct 94 ms 9188 KB Ok
50 Correct 100 ms 9188 KB Ok
51 Correct 95 ms 9336 KB Ok
52 Correct 91 ms 9192 KB Ok
53 Correct 109 ms 9188 KB Ok
54 Correct 276 ms 4708 KB Ok
55 Correct 293 ms 4836 KB Ok
56 Correct 288 ms 4836 KB Ok
57 Correct 217 ms 4324 KB Ok
58 Correct 254 ms 4324 KB Ok
59 Correct 239 ms 4196 KB Ok
60 Correct 216 ms 4068 KB Ok
61 Correct 222 ms 4324 KB Ok
62 Correct 283 ms 4708 KB Ok
63 Correct 236 ms 4324 KB Ok
64 Correct 282 ms 5220 KB Ok
65 Correct 262 ms 4452 KB Ok
66 Correct 245 ms 4340 KB Ok
67 Correct 215 ms 4324 KB Ok
68 Correct 243 ms 4452 KB Ok
69 Correct 458 ms 15332 KB Ok
70 Correct 471 ms 15716 KB Ok
71 Correct 448 ms 15180 KB Ok
72 Correct 468 ms 14948 KB Ok
73 Correct 440 ms 15204 KB Ok
74 Correct 443 ms 15076 KB Ok
75 Correct 463 ms 14692 KB Ok
76 Correct 479 ms 15332 KB Ok
77 Correct 442 ms 14564 KB Ok
78 Correct 472 ms 15236 KB Ok
79 Correct 462 ms 15204 KB Ok
80 Correct 459 ms 15476 KB Ok
81 Correct 468 ms 15332 KB Ok
82 Correct 457 ms 15204 KB Ok
83 Correct 442 ms 14692 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 9064 KB Ok
2 Correct 75 ms 9064 KB Ok
3 Correct 55 ms 3300 KB Ok
4 Correct 54 ms 3684 KB Ok
5 Correct 53 ms 3432 KB Ok
6 Correct 58 ms 4328 KB Ok
7 Correct 55 ms 3176 KB Ok
8 Correct 55 ms 4468 KB Ok
9 Correct 55 ms 3300 KB Ok
10 Correct 55 ms 5988 KB Ok
11 Correct 53 ms 3176 KB Ok
12 Correct 52 ms 3048 KB Ok
13 Correct 76 ms 9064 KB Ok
14 Correct 68 ms 9064 KB Ok
15 Correct 67 ms 9064 KB Ok
16 Correct 70 ms 9064 KB Ok
17 Correct 70 ms 9064 KB Ok
18 Correct 68 ms 9188 KB Ok
19 Correct 85 ms 9444 KB Ok
20 Correct 75 ms 9236 KB Ok
21 Correct 91 ms 9572 KB Ok
22 Correct 80 ms 9316 KB Ok
23 Correct 36 ms 9064 KB Ok
24 Correct 73 ms 9064 KB Ok
25 Correct 72 ms 9064 KB Ok
26 Correct 74 ms 9064 KB Ok
27 Correct 71 ms 9064 KB Ok
28 Correct 81 ms 9064 KB Ok
29 Correct 70 ms 9064 KB Ok
30 Correct 83 ms 9064 KB Ok
31 Correct 75 ms 9060 KB Ok
32 Correct 76 ms 9064 KB Ok
33 Correct 76 ms 9064 KB Ok
34 Correct 80 ms 9064 KB Ok
35 Correct 90 ms 9064 KB Ok
36 Correct 83 ms 9064 KB Ok
37 Correct 86 ms 9064 KB Ok
38 Correct 88 ms 9064 KB Ok
39 Correct 369 ms 12644 KB Ok
40 Correct 352 ms 11364 KB Ok
41 Correct 617 ms 14692 KB Ok
42 Correct 456 ms 13668 KB Ok
43 Correct 280 ms 10468 KB Ok
44 Correct 406 ms 12644 KB Ok
45 Correct 66 ms 2920 KB Ok
46 Correct 65 ms 3044 KB Ok
47 Correct 66 ms 3304 KB Ok
48 Correct 65 ms 3428 KB Ok
49 Correct 63 ms 2920 KB Ok
50 Correct 60 ms 4964 KB Ok
51 Correct 68 ms 3176 KB Ok
52 Correct 66 ms 2920 KB Ok
53 Correct 65 ms 3048 KB Ok
54 Correct 65 ms 3428 KB Ok
55 Correct 94 ms 9316 KB Ok
56 Correct 94 ms 9188 KB Ok
57 Correct 90 ms 9316 KB Ok
58 Correct 94 ms 9188 KB Ok
59 Correct 96 ms 9188 KB Ok
60 Correct 94 ms 9188 KB Ok
61 Correct 100 ms 9188 KB Ok
62 Correct 95 ms 9336 KB Ok
63 Correct 91 ms 9192 KB Ok
64 Correct 109 ms 9188 KB Ok
65 Correct 276 ms 4708 KB Ok
66 Correct 293 ms 4836 KB Ok
67 Correct 288 ms 4836 KB Ok
68 Correct 217 ms 4324 KB Ok
69 Correct 254 ms 4324 KB Ok
70 Correct 239 ms 4196 KB Ok
71 Correct 216 ms 4068 KB Ok
72 Correct 222 ms 4324 KB Ok
73 Correct 283 ms 4708 KB Ok
74 Correct 236 ms 4324 KB Ok
75 Correct 282 ms 5220 KB Ok
76 Correct 262 ms 4452 KB Ok
77 Correct 245 ms 4340 KB Ok
78 Correct 215 ms 4324 KB Ok
79 Correct 243 ms 4452 KB Ok
80 Correct 458 ms 15332 KB Ok
81 Correct 471 ms 15716 KB Ok
82 Correct 448 ms 15180 KB Ok
83 Correct 468 ms 14948 KB Ok
84 Correct 440 ms 15204 KB Ok
85 Correct 443 ms 15076 KB Ok
86 Correct 463 ms 14692 KB Ok
87 Correct 479 ms 15332 KB Ok
88 Correct 442 ms 14564 KB Ok
89 Correct 472 ms 15236 KB Ok
90 Correct 462 ms 15204 KB Ok
91 Correct 459 ms 15476 KB Ok
92 Correct 468 ms 15332 KB Ok
93 Correct 457 ms 15204 KB Ok
94 Correct 442 ms 14692 KB Ok
95 Correct 568 ms 8416 KB Ok
96 Correct 831 ms 10668 KB Ok
97 Correct 802 ms 9588 KB Ok
98 Correct 583 ms 8696 KB Ok
99 Correct 712 ms 8928 KB Ok
100 Correct 742 ms 9052 KB Ok
101 Correct 768 ms 9524 KB Ok
102 Correct 726 ms 9184 KB Ok
103 Correct 709 ms 9440 KB Ok
104 Correct 861 ms 10592 KB Ok
105 Correct 810 ms 10336 KB Ok
106 Correct 706 ms 10080 KB Ok
107 Correct 775 ms 9900 KB Ok
108 Correct 858 ms 10464 KB Ok
109 Correct 798 ms 10720 KB Ok
110 Correct 1912 ms 42976 KB Ok
111 Correct 1971 ms 45664 KB Ok
112 Correct 1974 ms 45448 KB Ok
113 Correct 1952 ms 44684 KB Ok
114 Correct 1953 ms 46932 KB Ok
115 Correct 1957 ms 44672 KB Ok
116 Execution timed out 2008 ms 45960 KB Time limit exceeded
117 Halted 0 ms 0 KB -