oj.uz

Submission #341936

# Submission time Handle Problem Language Result Execution time Memory
341936 2020-12-31T15:07:04 Z ivan_tudor Nice sequence (IZhO18_sequence) C++14
100 / 100
 1820 ms 46836 KB 
#include<bits/stdc++.h>
using namespace std;
const int N= 4*1e5 + 5;
bool viz[N];
int val[N];
int n, m;
vector<int> ord;
void dfs(int nod, int len){
  viz[nod] = true;
  if(nod + n<=len && viz[nod + n] == 0)
    dfs(nod + n, len);
  if(nod - m >=0 && viz[nod - m]==0)
    dfs(nod - m , len);
  ord.push_back(nod);
}
int ans[N];
void clr(int len){
  for(int i=0; i<=len;i++){
    val[i] = 0, viz[i] = 0;
  }
  ord.clear();
}
bool check(int len){
  int cnt = 0;
  for(int i=0;i<=len;i++){
    if(viz[i] == 0)
      dfs(i, len);
  }
  for(int i = 0; i< ord.size();i++){
    val[ord[i]]= i;
  }
  for(int i=1; i<=len;i++){
    if(i-n>=0 && val[i] > val[i - n]){
      clr(len);
      return false;
    }
    if(i - m >=0 && val[i] < val[i - m]){
      clr(len);
      return false;
    }
  }
  for(int i=1;i<=len;i++){
    ans[i] = val[i] - val[i -1];
  }
  clr(len);
  return true;
}
void solve(){
  cin>>n>>m;
  int pas = 0;
  for(int p2 = 1<<20; p2 > 0; p2>>=1){
    if(pas + p2 < N && check(pas + p2))
      pas += p2;
  }
  cout<<pas<<"\n";
  for(int i=1; i<=pas; i++){
    cout<<ans[i]<<" ";
  }
  cout<<"\n";
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int nrt;
  cin>>nrt;
  for(int i=1;i<=nrt;i++){
    solve();
  }
  return 0;
}

Compilation message

sequence.cpp: In function 'bool check(int)':
sequence.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i = 0; i< ord.size();i++){
      |                  ~^~~~~~~~~~~~
sequence.cpp:24:7: warning: unused variable 'cnt' [-Wunused-variable]
   24 |   int cnt = 0;
      |       ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10984 KB Ok
2 Correct 77 ms 10980 KB Ok
3 Correct 70 ms 3428 KB Ok
4 Correct 72 ms 3428 KB Ok
5 Correct 72 ms 3428 KB Ok
6 Correct 73 ms 4836 KB Ok
7 Correct 72 ms 3172 KB Ok
8 Correct 71 ms 4840 KB Ok
9 Correct 70 ms 3044 KB Ok
10 Correct 72 ms 6884 KB Ok
11 Correct 71 ms 3172 KB Ok
12 Correct 70 ms 3172 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 7016 KB Ok
2 Correct 72 ms 6884 KB Ok
3 Correct 74 ms 6888 KB Ok
4 Correct 71 ms 6884 KB Ok
5 Correct 79 ms 6888 KB Ok
6 Correct 77 ms 7012 KB Ok
7 Correct 95 ms 7524 KB Ok
8 Correct 83 ms 7148 KB Ok
9 Correct 99 ms 7524 KB Ok
10 Correct 96 ms 7524 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10980 KB Ok
2 Correct 91 ms 11000 KB Ok
3 Correct 74 ms 6884 KB Ok
4 Correct 72 ms 5480 KB Ok
5 Correct 81 ms 10984 KB Ok
6 Correct 87 ms 10980 KB Ok
7 Correct 77 ms 10984 KB Ok
8 Correct 75 ms 10980 KB Ok
9 Correct 74 ms 10980 KB Ok
10 Correct 75 ms 6884 KB Ok
11 Correct 71 ms 5476 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6908 KB Ok
2 Correct 69 ms 3940 KB Ok
3 Correct 68 ms 3432 KB Ok
4 Correct 69 ms 3304 KB Ok
5 Correct 69 ms 3196 KB Ok
6 Correct 369 ms 11620 KB Ok
7 Correct 331 ms 11876 KB Ok
8 Correct 611 ms 14948 KB Ok
9 Correct 443 ms 13540 KB Ok
10 Correct 268 ms 7780 KB Ok
11 Correct 404 ms 13412 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10984 KB Ok
2 Correct 77 ms 10980 KB Ok
3 Correct 70 ms 3428 KB Ok
4 Correct 72 ms 3428 KB Ok
5 Correct 72 ms 3428 KB Ok
6 Correct 73 ms 4836 KB Ok
7 Correct 72 ms 3172 KB Ok
8 Correct 71 ms 4840 KB Ok
9 Correct 70 ms 3044 KB Ok
10 Correct 72 ms 6884 KB Ok
11 Correct 71 ms 3172 KB Ok
12 Correct 70 ms 3172 KB Ok
13 Correct 30 ms 10980 KB Ok
14 Correct 91 ms 11000 KB Ok
15 Correct 74 ms 6884 KB Ok
16 Correct 72 ms 5480 KB Ok
17 Correct 81 ms 10984 KB Ok
18 Correct 87 ms 10980 KB Ok
19 Correct 77 ms 10984 KB Ok
20 Correct 75 ms 10980 KB Ok
21 Correct 74 ms 10980 KB Ok
22 Correct 75 ms 6884 KB Ok
23 Correct 71 ms 5476 KB Ok
24 Correct 70 ms 2916 KB Ok
25 Correct 72 ms 2916 KB Ok
26 Correct 71 ms 2916 KB Ok
27 Correct 77 ms 2920 KB Ok
28 Correct 74 ms 3000 KB Ok
29 Correct 70 ms 3044 KB Ok
30 Correct 70 ms 2792 KB Ok
31 Correct 72 ms 2916 KB Ok
32 Correct 71 ms 2916 KB Ok
33 Correct 74 ms 2916 KB Ok
34 Correct 81 ms 3044 KB Ok
35 Correct 81 ms 3044 KB Ok
36 Correct 80 ms 3044 KB Ok
37 Correct 81 ms 3044 KB Ok
38 Correct 80 ms 3088 KB Ok
39 Correct 81 ms 3044 KB Ok
40 Correct 82 ms 3044 KB Ok
41 Correct 80 ms 3044 KB Ok
42 Correct 83 ms 3172 KB Ok
43 Correct 81 ms 3044 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10984 KB Ok
2 Correct 77 ms 10980 KB Ok
3 Correct 70 ms 3428 KB Ok
4 Correct 72 ms 3428 KB Ok
5 Correct 72 ms 3428 KB Ok
6 Correct 73 ms 4836 KB Ok
7 Correct 72 ms 3172 KB Ok
8 Correct 71 ms 4840 KB Ok
9 Correct 70 ms 3044 KB Ok
10 Correct 72 ms 6884 KB Ok
11 Correct 71 ms 3172 KB Ok
12 Correct 70 ms 3172 KB Ok
13 Correct 81 ms 7016 KB Ok
14 Correct 72 ms 6884 KB Ok
15 Correct 74 ms 6888 KB Ok
16 Correct 71 ms 6884 KB Ok
17 Correct 79 ms 6888 KB Ok
18 Correct 77 ms 7012 KB Ok
19 Correct 95 ms 7524 KB Ok
20 Correct 83 ms 7148 KB Ok
21 Correct 99 ms 7524 KB Ok
22 Correct 96 ms 7524 KB Ok
23 Correct 30 ms 10980 KB Ok
24 Correct 91 ms 11000 KB Ok
25 Correct 74 ms 6884 KB Ok
26 Correct 72 ms 5480 KB Ok
27 Correct 81 ms 10984 KB Ok
28 Correct 87 ms 10980 KB Ok
29 Correct 77 ms 10984 KB Ok
30 Correct 75 ms 10980 KB Ok
31 Correct 74 ms 10980 KB Ok
32 Correct 75 ms 6884 KB Ok
33 Correct 71 ms 5476 KB Ok
34 Correct 70 ms 2916 KB Ok
35 Correct 72 ms 2916 KB Ok
36 Correct 71 ms 2916 KB Ok
37 Correct 77 ms 2920 KB Ok
38 Correct 74 ms 3000 KB Ok
39 Correct 70 ms 3044 KB Ok
40 Correct 70 ms 2792 KB Ok
41 Correct 72 ms 2916 KB Ok
42 Correct 71 ms 2916 KB Ok
43 Correct 74 ms 2916 KB Ok
44 Correct 81 ms 3044 KB Ok
45 Correct 81 ms 3044 KB Ok
46 Correct 80 ms 3044 KB Ok
47 Correct 81 ms 3044 KB Ok
48 Correct 80 ms 3088 KB Ok
49 Correct 81 ms 3044 KB Ok
50 Correct 82 ms 3044 KB Ok
51 Correct 80 ms 3044 KB Ok
52 Correct 83 ms 3172 KB Ok
53 Correct 81 ms 3044 KB Ok
54 Correct 272 ms 4964 KB Ok
55 Correct 307 ms 5220 KB Ok
56 Correct 300 ms 5348 KB Ok
57 Correct 227 ms 4452 KB Ok
58 Correct 266 ms 4708 KB Ok
59 Correct 251 ms 4580 KB Ok
60 Correct 231 ms 4324 KB Ok
61 Correct 232 ms 4452 KB Ok
62 Correct 288 ms 4964 KB Ok
63 Correct 249 ms 4580 KB Ok
64 Correct 297 ms 5408 KB Ok
65 Correct 271 ms 4836 KB Ok
66 Correct 254 ms 4704 KB Ok
67 Correct 229 ms 4580 KB Ok
68 Correct 259 ms 4836 KB Ok
69 Correct 472 ms 12260 KB Ok
70 Correct 483 ms 12868 KB Ok
71 Correct 469 ms 12388 KB Ok
72 Correct 478 ms 12260 KB Ok
73 Correct 474 ms 12516 KB Ok
74 Correct 474 ms 12260 KB Ok
75 Correct 476 ms 11756 KB Ok
76 Correct 484 ms 12816 KB Ok
77 Correct 465 ms 11876 KB Ok
78 Correct 477 ms 12388 KB Ok
79 Correct 479 ms 12516 KB Ok
80 Correct 481 ms 12516 KB Ok
81 Correct 480 ms 12388 KB Ok
82 Correct 464 ms 12388 KB Ok
83 Correct 465 ms 12132 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10984 KB Ok
2 Correct 77 ms 10980 KB Ok
3 Correct 70 ms 3428 KB Ok
4 Correct 72 ms 3428 KB Ok
5 Correct 72 ms 3428 KB Ok
6 Correct 73 ms 4836 KB Ok
7 Correct 72 ms 3172 KB Ok
8 Correct 71 ms 4840 KB Ok
9 Correct 70 ms 3044 KB Ok
10 Correct 72 ms 6884 KB Ok
11 Correct 71 ms 3172 KB Ok
12 Correct 70 ms 3172 KB Ok
13 Correct 81 ms 7016 KB Ok
14 Correct 72 ms 6884 KB Ok
15 Correct 74 ms 6888 KB Ok
16 Correct 71 ms 6884 KB Ok
17 Correct 79 ms 6888 KB Ok
18 Correct 77 ms 7012 KB Ok
19 Correct 95 ms 7524 KB Ok
20 Correct 83 ms 7148 KB Ok
21 Correct 99 ms 7524 KB Ok
22 Correct 96 ms 7524 KB Ok
23 Correct 30 ms 10980 KB Ok
24 Correct 91 ms 11000 KB Ok
25 Correct 74 ms 6884 KB Ok
26 Correct 72 ms 5480 KB Ok
27 Correct 81 ms 10984 KB Ok
28 Correct 87 ms 10980 KB Ok
29 Correct 77 ms 10984 KB Ok
30 Correct 75 ms 10980 KB Ok
31 Correct 74 ms 10980 KB Ok
32 Correct 75 ms 6884 KB Ok
33 Correct 71 ms 5476 KB Ok
34 Correct 82 ms 6908 KB Ok
35 Correct 69 ms 3940 KB Ok
36 Correct 68 ms 3432 KB Ok
37 Correct 69 ms 3304 KB Ok
38 Correct 69 ms 3196 KB Ok
39 Correct 369 ms 11620 KB Ok
40 Correct 331 ms 11876 KB Ok
41 Correct 611 ms 14948 KB Ok
42 Correct 443 ms 13540 KB Ok
43 Correct 268 ms 7780 KB Ok
44 Correct 404 ms 13412 KB Ok
45 Correct 70 ms 2916 KB Ok
46 Correct 72 ms 2916 KB Ok
47 Correct 71 ms 2916 KB Ok
48 Correct 77 ms 2920 KB Ok
49 Correct 74 ms 3000 KB Ok
50 Correct 70 ms 3044 KB Ok
51 Correct 70 ms 2792 KB Ok
52 Correct 72 ms 2916 KB Ok
53 Correct 71 ms 2916 KB Ok
54 Correct 74 ms 2916 KB Ok
55 Correct 81 ms 3044 KB Ok
56 Correct 81 ms 3044 KB Ok
57 Correct 80 ms 3044 KB Ok
58 Correct 81 ms 3044 KB Ok
59 Correct 80 ms 3088 KB Ok
60 Correct 81 ms 3044 KB Ok
61 Correct 82 ms 3044 KB Ok
62 Correct 80 ms 3044 KB Ok
63 Correct 83 ms 3172 KB Ok
64 Correct 81 ms 3044 KB Ok
65 Correct 272 ms 4964 KB Ok
66 Correct 307 ms 5220 KB Ok
67 Correct 300 ms 5348 KB Ok
68 Correct 227 ms 4452 KB Ok
69 Correct 266 ms 4708 KB Ok
70 Correct 251 ms 4580 KB Ok
71 Correct 231 ms 4324 KB Ok
72 Correct 232 ms 4452 KB Ok
73 Correct 288 ms 4964 KB Ok
74 Correct 249 ms 4580 KB Ok
75 Correct 297 ms 5408 KB Ok
76 Correct 271 ms 4836 KB Ok
77 Correct 254 ms 4704 KB Ok
78 Correct 229 ms 4580 KB Ok
79 Correct 259 ms 4836 KB Ok
80 Correct 472 ms 12260 KB Ok
81 Correct 483 ms 12868 KB Ok
82 Correct 469 ms 12388 KB Ok
83 Correct 478 ms 12260 KB Ok
84 Correct 474 ms 12516 KB Ok
85 Correct 474 ms 12260 KB Ok
86 Correct 476 ms 11756 KB Ok
87 Correct 484 ms 12816 KB Ok
88 Correct 465 ms 11876 KB Ok
89 Correct 477 ms 12388 KB Ok
90 Correct 479 ms 12516 KB Ok
91 Correct 481 ms 12516 KB Ok
92 Correct 480 ms 12388 KB Ok
93 Correct 464 ms 12388 KB Ok
94 Correct 465 ms 12132 KB Ok
95 Correct 566 ms 8036 KB Ok
96 Correct 827 ms 10980 KB Ok
97 Correct 783 ms 10468 KB Ok
98 Correct 605 ms 9396 KB Ok
99 Correct 699 ms 9868 KB Ok
100 Correct 718 ms 9904 KB Ok
101 Correct 747 ms 10212 KB Ok
102 Correct 744 ms 10212 KB Ok
103 Correct 707 ms 10084 KB Ok
104 Correct 859 ms 11364 KB Ok
105 Correct 797 ms 10980 KB Ok
106 Correct 710 ms 10596 KB Ok
107 Correct 779 ms 10596 KB Ok
108 Correct 856 ms 11236 KB Ok
109 Correct 769 ms 11000 KB Ok
110 Correct 1642 ms 43108 KB Ok
111 Correct 1785 ms 45924 KB Ok
112 Correct 1751 ms 45668 KB Ok
113 Correct 1724 ms 45196 KB Ok
114 Correct 1655 ms 46836 KB Ok
115 Correct 1684 ms 44644 KB Ok
116 Correct 1731 ms 46052 KB Ok
117 Correct 1760 ms 44644 KB Ok
118 Correct 1610 ms 44900 KB Ok
119 Correct 1739 ms 44616 KB Ok
120 Correct 1687 ms 44516 KB Ok
121 Correct 1667 ms 42980 KB Ok
122 Correct 1820 ms 45664 KB Ok
123 Correct 1784 ms 45924 KB Ok
124 Correct 1703 ms 43364 KB Ok
125 Correct 1324 ms 28260 KB Ok