oj.uz

Submission #334930

# Submission time Handle Problem Language Result Execution time Memory
334930 2020-12-10T10:31:38 Z beksultan04 Nice sequence (IZhO18_sequence) C++14
76 / 100
 686 ms 17884 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 = 2e5+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(){
    int t;
    scan1(t)
    while (t--){
        int i,j;
        scan2(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(long long int)':
sequence.cpp:37:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long 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:51:15: warning: unused variable 'j' [-Wunused-variable]
   51 |         int i,j;
      |               ^
sequence.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | #define scan1(a) scanf("%lld",&a);
      |                  ~~~~~^~~~~~~~~~~
sequence.cpp:49:5: note: in expansion of macro 'scan1'
   49 |     scan1(t)
      |     ^~~~~
sequence.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 | #define scan2(a,b) scanf("%lld %lld",&a, &b);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:52:9: note: in expansion of macro 'scan2'
   52 |         scan2(n,m)
      |         ^~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 11356 KB Ok
2 Correct 73 ms 11356 KB Ok
3 Correct 69 ms 5596 KB Ok
4 Correct 59 ms 5980 KB Ok
5 Correct 60 ms 5568 KB Ok
6 Correct 61 ms 6748 KB Ok
7 Correct 60 ms 5596 KB Ok
8 Correct 58 ms 6748 KB Ok
9 Correct 58 ms 5664 KB Ok
10 Correct 58 ms 8284 KB Ok
11 Correct 58 ms 5468 KB Ok
12 Correct 58 ms 5340 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 11356 KB Ok
2 Correct 78 ms 11356 KB Ok
3 Correct 67 ms 11356 KB Ok
4 Correct 77 ms 11356 KB Ok
5 Correct 69 ms 11356 KB Ok
6 Correct 73 ms 11484 KB Ok
7 Correct 93 ms 11740 KB Ok
8 Correct 82 ms 11612 KB Ok
9 Correct 100 ms 11868 KB Ok
10 Correct 94 ms 11868 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11356 KB Ok
2 Correct 76 ms 11356 KB Ok
3 Correct 71 ms 11356 KB Ok
4 Correct 83 ms 11356 KB Ok
5 Correct 73 ms 11356 KB Ok
6 Correct 79 ms 11356 KB Ok
7 Correct 77 ms 11356 KB Ok
8 Correct 83 ms 11356 KB Ok
9 Correct 74 ms 11484 KB Ok
10 Correct 77 ms 11484 KB Ok
11 Correct 78 ms 11356 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 11356 KB Ok
2 Correct 84 ms 11484 KB Ok
3 Correct 84 ms 11356 KB Ok
4 Correct 86 ms 11356 KB Ok
5 Correct 85 ms 11356 KB Ok
6 Correct 407 ms 14940 KB Ok
7 Correct 364 ms 13532 KB Ok
8 Correct 686 ms 16988 KB Ok
9 Correct 495 ms 15964 KB Ok
10 Correct 295 ms 12764 KB Ok
11 Correct 447 ms 15068 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 11356 KB Ok
2 Correct 73 ms 11356 KB Ok
3 Correct 69 ms 5596 KB Ok
4 Correct 59 ms 5980 KB Ok
5 Correct 60 ms 5568 KB Ok
6 Correct 61 ms 6748 KB Ok
7 Correct 60 ms 5596 KB Ok
8 Correct 58 ms 6748 KB Ok
9 Correct 58 ms 5664 KB Ok
10 Correct 58 ms 8284 KB Ok
11 Correct 58 ms 5468 KB Ok
12 Correct 58 ms 5340 KB Ok
13 Correct 27 ms 11356 KB Ok
14 Correct 76 ms 11356 KB Ok
15 Correct 71 ms 11356 KB Ok
16 Correct 83 ms 11356 KB Ok
17 Correct 73 ms 11356 KB Ok
18 Correct 79 ms 11356 KB Ok
19 Correct 77 ms 11356 KB Ok
20 Correct 83 ms 11356 KB Ok
21 Correct 74 ms 11484 KB Ok
22 Correct 77 ms 11484 KB Ok
23 Correct 78 ms 11356 KB Ok
24 Correct 66 ms 5212 KB Ok
25 Correct 70 ms 5344 KB Ok
26 Correct 69 ms 5724 KB Ok
27 Correct 69 ms 5668 KB Ok
28 Correct 67 ms 5340 KB Ok
29 Correct 63 ms 7260 KB Ok
30 Correct 70 ms 5596 KB Ok
31 Correct 70 ms 5212 KB Ok
32 Correct 68 ms 5212 KB Ok
33 Correct 69 ms 5724 KB Ok
34 Correct 101 ms 11612 KB Ok
35 Correct 107 ms 11484 KB Ok
36 Correct 100 ms 11484 KB Ok
37 Correct 108 ms 11484 KB Ok
38 Correct 102 ms 11484 KB Ok
39 Correct 99 ms 11484 KB Ok
40 Correct 100 ms 11484 KB Ok
41 Correct 105 ms 11484 KB Ok
42 Correct 99 ms 11484 KB Ok
43 Correct 102 ms 11484 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 11356 KB Ok
2 Correct 73 ms 11356 KB Ok
3 Correct 69 ms 5596 KB Ok
4 Correct 59 ms 5980 KB Ok
5 Correct 60 ms 5568 KB Ok
6 Correct 61 ms 6748 KB Ok
7 Correct 60 ms 5596 KB Ok
8 Correct 58 ms 6748 KB Ok
9 Correct 58 ms 5664 KB Ok
10 Correct 58 ms 8284 KB Ok
11 Correct 58 ms 5468 KB Ok
12 Correct 58 ms 5340 KB Ok
13 Correct 75 ms 11356 KB Ok
14 Correct 78 ms 11356 KB Ok
15 Correct 67 ms 11356 KB Ok
16 Correct 77 ms 11356 KB Ok
17 Correct 69 ms 11356 KB Ok
18 Correct 73 ms 11484 KB Ok
19 Correct 93 ms 11740 KB Ok
20 Correct 82 ms 11612 KB Ok
21 Correct 100 ms 11868 KB Ok
22 Correct 94 ms 11868 KB Ok
23 Correct 27 ms 11356 KB Ok
24 Correct 76 ms 11356 KB Ok
25 Correct 71 ms 11356 KB Ok
26 Correct 83 ms 11356 KB Ok
27 Correct 73 ms 11356 KB Ok
28 Correct 79 ms 11356 KB Ok
29 Correct 77 ms 11356 KB Ok
30 Correct 83 ms 11356 KB Ok
31 Correct 74 ms 11484 KB Ok
32 Correct 77 ms 11484 KB Ok
33 Correct 78 ms 11356 KB Ok
34 Correct 66 ms 5212 KB Ok
35 Correct 70 ms 5344 KB Ok
36 Correct 69 ms 5724 KB Ok
37 Correct 69 ms 5668 KB Ok
38 Correct 67 ms 5340 KB Ok
39 Correct 63 ms 7260 KB Ok
40 Correct 70 ms 5596 KB Ok
41 Correct 70 ms 5212 KB Ok
42 Correct 68 ms 5212 KB Ok
43 Correct 69 ms 5724 KB Ok
44 Correct 101 ms 11612 KB Ok
45 Correct 107 ms 11484 KB Ok
46 Correct 100 ms 11484 KB Ok
47 Correct 108 ms 11484 KB Ok
48 Correct 102 ms 11484 KB Ok
49 Correct 99 ms 11484 KB Ok
50 Correct 100 ms 11484 KB Ok
51 Correct 105 ms 11484 KB Ok
52 Correct 99 ms 11484 KB Ok
53 Correct 102 ms 11484 KB Ok
54 Correct 275 ms 6876 KB Ok
55 Correct 317 ms 7260 KB Ok
56 Correct 311 ms 7132 KB Ok
57 Correct 229 ms 6548 KB Ok
58 Correct 266 ms 6620 KB Ok
59 Correct 250 ms 6688 KB Ok
60 Correct 233 ms 6364 KB Ok
61 Correct 235 ms 6564 KB Ok
62 Correct 296 ms 6876 KB Ok
63 Correct 248 ms 6876 KB Ok
64 Correct 305 ms 7132 KB Ok
65 Correct 276 ms 6872 KB Ok
66 Correct 260 ms 6748 KB Ok
67 Correct 228 ms 6620 KB Ok
68 Correct 262 ms 6748 KB Ok
69 Correct 507 ms 17372 KB Ok
70 Correct 534 ms 17884 KB Ok
71 Correct 495 ms 17496 KB Ok
72 Correct 518 ms 17244 KB Ok
73 Correct 496 ms 17372 KB Ok
74 Correct 489 ms 17244 KB Ok
75 Correct 508 ms 17012 KB Ok
76 Correct 523 ms 17800 KB Ok
77 Correct 476 ms 17116 KB Ok
78 Correct 510 ms 17484 KB Ok
79 Correct 515 ms 17756 KB Ok
80 Correct 499 ms 17628 KB Ok
81 Correct 507 ms 17756 KB Ok
82 Correct 500 ms 17628 KB Ok
83 Correct 498 ms 17116 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 11356 KB Ok
2 Correct 73 ms 11356 KB Ok
3 Correct 69 ms 5596 KB Ok
4 Correct 59 ms 5980 KB Ok
5 Correct 60 ms 5568 KB Ok
6 Correct 61 ms 6748 KB Ok
7 Correct 60 ms 5596 KB Ok
8 Correct 58 ms 6748 KB Ok
9 Correct 58 ms 5664 KB Ok
10 Correct 58 ms 8284 KB Ok
11 Correct 58 ms 5468 KB Ok
12 Correct 58 ms 5340 KB Ok
13 Correct 75 ms 11356 KB Ok
14 Correct 78 ms 11356 KB Ok
15 Correct 67 ms 11356 KB Ok
16 Correct 77 ms 11356 KB Ok
17 Correct 69 ms 11356 KB Ok
18 Correct 73 ms 11484 KB Ok
19 Correct 93 ms 11740 KB Ok
20 Correct 82 ms 11612 KB Ok
21 Correct 100 ms 11868 KB Ok
22 Correct 94 ms 11868 KB Ok
23 Correct 27 ms 11356 KB Ok
24 Correct 76 ms 11356 KB Ok
25 Correct 71 ms 11356 KB Ok
26 Correct 83 ms 11356 KB Ok
27 Correct 73 ms 11356 KB Ok
28 Correct 79 ms 11356 KB Ok
29 Correct 77 ms 11356 KB Ok
30 Correct 83 ms 11356 KB Ok
31 Correct 74 ms 11484 KB Ok
32 Correct 77 ms 11484 KB Ok
33 Correct 78 ms 11356 KB Ok
34 Correct 80 ms 11356 KB Ok
35 Correct 84 ms 11484 KB Ok
36 Correct 84 ms 11356 KB Ok
37 Correct 86 ms 11356 KB Ok
38 Correct 85 ms 11356 KB Ok
39 Correct 407 ms 14940 KB Ok
40 Correct 364 ms 13532 KB Ok
41 Correct 686 ms 16988 KB Ok
42 Correct 495 ms 15964 KB Ok
43 Correct 295 ms 12764 KB Ok
44 Correct 447 ms 15068 KB Ok
45 Correct 66 ms 5212 KB Ok
46 Correct 70 ms 5344 KB Ok
47 Correct 69 ms 5724 KB Ok
48 Correct 69 ms 5668 KB Ok
49 Correct 67 ms 5340 KB Ok
50 Correct 63 ms 7260 KB Ok
51 Correct 70 ms 5596 KB Ok
52 Correct 70 ms 5212 KB Ok
53 Correct 68 ms 5212 KB Ok
54 Correct 69 ms 5724 KB Ok
55 Correct 101 ms 11612 KB Ok
56 Correct 107 ms 11484 KB Ok
57 Correct 100 ms 11484 KB Ok
58 Correct 108 ms 11484 KB Ok
59 Correct 102 ms 11484 KB Ok
60 Correct 99 ms 11484 KB Ok
61 Correct 100 ms 11484 KB Ok
62 Correct 105 ms 11484 KB Ok
63 Correct 99 ms 11484 KB Ok
64 Correct 102 ms 11484 KB Ok
65 Correct 275 ms 6876 KB Ok
66 Correct 317 ms 7260 KB Ok
67 Correct 311 ms 7132 KB Ok
68 Correct 229 ms 6548 KB Ok
69 Correct 266 ms 6620 KB Ok
70 Correct 250 ms 6688 KB Ok
71 Correct 233 ms 6364 KB Ok
72 Correct 235 ms 6564 KB Ok
73 Correct 296 ms 6876 KB Ok
74 Correct 248 ms 6876 KB Ok
75 Correct 305 ms 7132 KB Ok
76 Correct 276 ms 6872 KB Ok
77 Correct 260 ms 6748 KB Ok
78 Correct 228 ms 6620 KB Ok
79 Correct 262 ms 6748 KB Ok
80 Correct 507 ms 17372 KB Ok
81 Correct 534 ms 17884 KB Ok
82 Correct 495 ms 17496 KB Ok
83 Correct 518 ms 17244 KB Ok
84 Correct 496 ms 17372 KB Ok
85 Correct 489 ms 17244 KB Ok
86 Correct 508 ms 17012 KB Ok
87 Correct 523 ms 17800 KB Ok
88 Correct 476 ms 17116 KB Ok
89 Correct 510 ms 17484 KB Ok
90 Correct 515 ms 17756 KB Ok
91 Correct 499 ms 17628 KB Ok
92 Correct 507 ms 17756 KB Ok
93 Correct 500 ms 17628 KB Ok
94 Correct 498 ms 17116 KB Ok
95 Runtime error 215 ms 11740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Halted 0 ms 0 KB -