oj.uz

Submission #1006740

# Submission time Handle Problem Language Result Execution time Memory
1006740 2024-06-24T08:00:50 Z shenfe1 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 55480 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second 
#define ll long long
#define lb lower_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define int ll
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))

using namespace std;

const int MAX=5e5+100;
const int inf=1e18;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

int n,m;
int p[MAX];
int use[MAX];
bool ok;
vector<int> g[MAX];
vector<int> top;

void dfs(int v){
  use[v]=1;
  for(auto to:g[v]){
    if(!use[to])dfs(to);
    else if(use[to]==1){
      ok=0;
    }
  }
  top.pb(v);
  use[v]=2;
}

bool check(int mid){
  ok=1;
  top.clear();
  for(int i=0;i<=mid;i++)g[i].clear(),use[i]=0;
  for(int i=m;i<=mid;i++){
    g[i-m].pb(i);
  }
  for(int i=n;i<=mid;i++){
    g[i].pb(i-n);
  }
  for(int i=0;i<=mid;i++){
    if(!use[i]){
      dfs(i);
    }
  }
  if(!ok)return 0;
  for(int i=0;i<=mid;i++){
    p[top[i]]=i;
  }
  for(int i=1;i<=mid;i++)p[i]-=p[0];
  p[0]=0;
  return 1;
}

void solve(){
  cin>>n>>m;
  bool ok=0;
  if(n<m){
    ok=1;
    swap(n,m);
  }
  int l=min(n,m),r=5e5,res=min(n,m)-1;
  while(l<=r){
    int mid=(l+r)/2;
    if(check(mid)){
      l=mid+1;
      res=mid;
    }
    else r=mid-1;
  }
  check(res);
  for(int i=res;i>=1;i--)p[i]-=p[i-1];
  if(!ok)for(int i=1;i<=res;i++)p[i]=-p[i];
  cout<<res<<'\n';
  for(int i=1;i<=res;i++)cout<<p[i]<<" ";
  cout<<"\n";
}

// #ifdef LOCAL
signed main(){
// freopen("pushabox.in","r",stdin);
// freopen("pushabox.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  cin>>t;
  while(t--)solve();
}
// #endif

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 38604 KB Ok
2 Correct 92 ms 38548 KB Ok
3 Correct 81 ms 27840 KB Ok
4 Correct 85 ms 28616 KB Ok
5 Correct 80 ms 27596 KB Ok
6 Correct 96 ms 29640 KB Ok
7 Correct 84 ms 27348 KB Ok
8 Correct 83 ms 29908 KB Ok
9 Correct 80 ms 27564 KB Ok
10 Correct 87 ms 32708 KB Ok
11 Correct 84 ms 27340 KB Ok
12 Correct 82 ms 27084 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 32676 KB Ok
2 Correct 78 ms 32724 KB Ok
3 Correct 76 ms 32712 KB Ok
4 Correct 76 ms 32712 KB Ok
5 Correct 79 ms 32712 KB Ok
6 Correct 80 ms 32724 KB Ok
7 Correct 91 ms 33480 KB Ok
8 Correct 78 ms 32940 KB Ok
9 Correct 92 ms 33480 KB Ok
10 Correct 86 ms 33228 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 38588 KB Ok
2 Correct 85 ms 38712 KB Ok
3 Correct 81 ms 38588 KB Ok
4 Correct 78 ms 38548 KB Ok
5 Correct 79 ms 38612 KB Ok
6 Correct 79 ms 38600 KB Ok
7 Correct 77 ms 38552 KB Ok
8 Correct 72 ms 38604 KB Ok
9 Correct 77 ms 38600 KB Ok
10 Correct 76 ms 38600 KB Ok
11 Correct 76 ms 38600 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 32724 KB Ok
2 Correct 76 ms 28628 KB Ok
3 Correct 68 ms 27856 KB Ok
4 Correct 70 ms 27604 KB Ok
5 Correct 81 ms 27348 KB Ok
6 Correct 186 ms 42156 KB Ok
7 Correct 214 ms 42656 KB Ok
8 Correct 296 ms 43448 KB Ok
9 Correct 259 ms 43700 KB Ok
10 Correct 162 ms 37560 KB Ok
11 Correct 258 ms 43960 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 38604 KB Ok
2 Correct 92 ms 38548 KB Ok
3 Correct 81 ms 27840 KB Ok
4 Correct 85 ms 28616 KB Ok
5 Correct 80 ms 27596 KB Ok
6 Correct 96 ms 29640 KB Ok
7 Correct 84 ms 27348 KB Ok
8 Correct 83 ms 29908 KB Ok
9 Correct 80 ms 27564 KB Ok
10 Correct 87 ms 32708 KB Ok
11 Correct 84 ms 27340 KB Ok
12 Correct 82 ms 27084 KB Ok
13 Correct 44 ms 38588 KB Ok
14 Correct 85 ms 38712 KB Ok
15 Correct 81 ms 38588 KB Ok
16 Correct 78 ms 38548 KB Ok
17 Correct 79 ms 38612 KB Ok
18 Correct 79 ms 38600 KB Ok
19 Correct 77 ms 38552 KB Ok
20 Correct 72 ms 38604 KB Ok
21 Correct 77 ms 38600 KB Ok
22 Correct 76 ms 38600 KB Ok
23 Correct 76 ms 38600 KB Ok
24 Correct 79 ms 26828 KB Ok
25 Correct 87 ms 27072 KB Ok
26 Correct 79 ms 26832 KB Ok
27 Correct 84 ms 27068 KB Ok
28 Correct 77 ms 27068 KB Ok
29 Correct 76 ms 27324 KB Ok
30 Correct 85 ms 27336 KB Ok
31 Correct 84 ms 27064 KB Ok
32 Correct 85 ms 27032 KB Ok
33 Correct 81 ms 26824 KB Ok
34 Correct 117 ms 27072 KB Ok
35 Correct 129 ms 27072 KB Ok
36 Correct 123 ms 27328 KB Ok
37 Correct 129 ms 27156 KB Ok
38 Correct 124 ms 27308 KB Ok
39 Correct 129 ms 27068 KB Ok
40 Correct 127 ms 27128 KB Ok
41 Correct 122 ms 27212 KB Ok
42 Correct 130 ms 27324 KB Ok
43 Correct 136 ms 27324 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 38604 KB Ok
2 Correct 92 ms 38548 KB Ok
3 Correct 81 ms 27840 KB Ok
4 Correct 85 ms 28616 KB Ok
5 Correct 80 ms 27596 KB Ok
6 Correct 96 ms 29640 KB Ok
7 Correct 84 ms 27348 KB Ok
8 Correct 83 ms 29908 KB Ok
9 Correct 80 ms 27564 KB Ok
10 Correct 87 ms 32708 KB Ok
11 Correct 84 ms 27340 KB Ok
12 Correct 82 ms 27084 KB Ok
13 Correct 77 ms 32676 KB Ok
14 Correct 78 ms 32724 KB Ok
15 Correct 76 ms 32712 KB Ok
16 Correct 76 ms 32712 KB Ok
17 Correct 79 ms 32712 KB Ok
18 Correct 80 ms 32724 KB Ok
19 Correct 91 ms 33480 KB Ok
20 Correct 78 ms 32940 KB Ok
21 Correct 92 ms 33480 KB Ok
22 Correct 86 ms 33228 KB Ok
23 Correct 44 ms 38588 KB Ok
24 Correct 85 ms 38712 KB Ok
25 Correct 81 ms 38588 KB Ok
26 Correct 78 ms 38548 KB Ok
27 Correct 79 ms 38612 KB Ok
28 Correct 79 ms 38600 KB Ok
29 Correct 77 ms 38552 KB Ok
30 Correct 72 ms 38604 KB Ok
31 Correct 77 ms 38600 KB Ok
32 Correct 76 ms 38600 KB Ok
33 Correct 76 ms 38600 KB Ok
34 Correct 79 ms 26828 KB Ok
35 Correct 87 ms 27072 KB Ok
36 Correct 79 ms 26832 KB Ok
37 Correct 84 ms 27068 KB Ok
38 Correct 77 ms 27068 KB Ok
39 Correct 76 ms 27324 KB Ok
40 Correct 85 ms 27336 KB Ok
41 Correct 84 ms 27064 KB Ok
42 Correct 85 ms 27032 KB Ok
43 Correct 81 ms 26824 KB Ok
44 Correct 117 ms 27072 KB Ok
45 Correct 129 ms 27072 KB Ok
46 Correct 123 ms 27328 KB Ok
47 Correct 129 ms 27156 KB Ok
48 Correct 124 ms 27308 KB Ok
49 Correct 129 ms 27068 KB Ok
50 Correct 127 ms 27128 KB Ok
51 Correct 122 ms 27212 KB Ok
52 Correct 130 ms 27324 KB Ok
53 Correct 136 ms 27324 KB Ok
54 Correct 217 ms 29740 KB Ok
55 Correct 187 ms 31676 KB Ok
56 Correct 233 ms 31948 KB Ok
57 Correct 150 ms 30452 KB Ok
58 Correct 171 ms 31156 KB Ok
59 Correct 152 ms 29404 KB Ok
60 Correct 151 ms 29104 KB Ok
61 Correct 143 ms 29700 KB Ok
62 Correct 204 ms 30420 KB Ok
63 Correct 160 ms 29388 KB Ok
64 Correct 216 ms 31668 KB Ok
65 Correct 175 ms 31396 KB Ok
66 Correct 166 ms 30652 KB Ok
67 Correct 159 ms 29584 KB Ok
68 Correct 181 ms 31156 KB Ok
69 Correct 719 ms 38720 KB Ok
70 Correct 746 ms 40512 KB Ok
71 Correct 778 ms 38840 KB Ok
72 Correct 700 ms 39800 KB Ok
73 Correct 739 ms 38668 KB Ok
74 Correct 760 ms 38432 KB Ok
75 Correct 779 ms 39636 KB Ok
76 Correct 750 ms 40120 KB Ok
77 Correct 708 ms 38780 KB Ok
78 Correct 717 ms 39056 KB Ok
79 Correct 751 ms 39620 KB Ok
80 Correct 685 ms 38840 KB Ok
81 Correct 727 ms 39032 KB Ok
82 Correct 691 ms 39976 KB Ok
83 Correct 693 ms 38076 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 38604 KB Ok
2 Correct 92 ms 38548 KB Ok
3 Correct 81 ms 27840 KB Ok
4 Correct 85 ms 28616 KB Ok
5 Correct 80 ms 27596 KB Ok
6 Correct 96 ms 29640 KB Ok
7 Correct 84 ms 27348 KB Ok
8 Correct 83 ms 29908 KB Ok
9 Correct 80 ms 27564 KB Ok
10 Correct 87 ms 32708 KB Ok
11 Correct 84 ms 27340 KB Ok
12 Correct 82 ms 27084 KB Ok
13 Correct 77 ms 32676 KB Ok
14 Correct 78 ms 32724 KB Ok
15 Correct 76 ms 32712 KB Ok
16 Correct 76 ms 32712 KB Ok
17 Correct 79 ms 32712 KB Ok
18 Correct 80 ms 32724 KB Ok
19 Correct 91 ms 33480 KB Ok
20 Correct 78 ms 32940 KB Ok
21 Correct 92 ms 33480 KB Ok
22 Correct 86 ms 33228 KB Ok
23 Correct 44 ms 38588 KB Ok
24 Correct 85 ms 38712 KB Ok
25 Correct 81 ms 38588 KB Ok
26 Correct 78 ms 38548 KB Ok
27 Correct 79 ms 38612 KB Ok
28 Correct 79 ms 38600 KB Ok
29 Correct 77 ms 38552 KB Ok
30 Correct 72 ms 38604 KB Ok
31 Correct 77 ms 38600 KB Ok
32 Correct 76 ms 38600 KB Ok
33 Correct 76 ms 38600 KB Ok
34 Correct 63 ms 32724 KB Ok
35 Correct 76 ms 28628 KB Ok
36 Correct 68 ms 27856 KB Ok
37 Correct 70 ms 27604 KB Ok
38 Correct 81 ms 27348 KB Ok
39 Correct 186 ms 42156 KB Ok
40 Correct 214 ms 42656 KB Ok
41 Correct 296 ms 43448 KB Ok
42 Correct 259 ms 43700 KB Ok
43 Correct 162 ms 37560 KB Ok
44 Correct 258 ms 43960 KB Ok
45 Correct 79 ms 26828 KB Ok
46 Correct 87 ms 27072 KB Ok
47 Correct 79 ms 26832 KB Ok
48 Correct 84 ms 27068 KB Ok
49 Correct 77 ms 27068 KB Ok
50 Correct 76 ms 27324 KB Ok
51 Correct 85 ms 27336 KB Ok
52 Correct 84 ms 27064 KB Ok
53 Correct 85 ms 27032 KB Ok
54 Correct 81 ms 26824 KB Ok
55 Correct 117 ms 27072 KB Ok
56 Correct 129 ms 27072 KB Ok
57 Correct 123 ms 27328 KB Ok
58 Correct 129 ms 27156 KB Ok
59 Correct 124 ms 27308 KB Ok
60 Correct 129 ms 27068 KB Ok
61 Correct 127 ms 27128 KB Ok
62 Correct 122 ms 27212 KB Ok
63 Correct 130 ms 27324 KB Ok
64 Correct 136 ms 27324 KB Ok
65 Correct 217 ms 29740 KB Ok
66 Correct 187 ms 31676 KB Ok
67 Correct 233 ms 31948 KB Ok
68 Correct 150 ms 30452 KB Ok
69 Correct 171 ms 31156 KB Ok
70 Correct 152 ms 29404 KB Ok
71 Correct 151 ms 29104 KB Ok
72 Correct 143 ms 29700 KB Ok
73 Correct 204 ms 30420 KB Ok
74 Correct 160 ms 29388 KB Ok
75 Correct 216 ms 31668 KB Ok
76 Correct 175 ms 31396 KB Ok
77 Correct 166 ms 30652 KB Ok
78 Correct 159 ms 29584 KB Ok
79 Correct 181 ms 31156 KB Ok
80 Correct 719 ms 38720 KB Ok
81 Correct 746 ms 40512 KB Ok
82 Correct 778 ms 38840 KB Ok
83 Correct 700 ms 39800 KB Ok
84 Correct 739 ms 38668 KB Ok
85 Correct 760 ms 38432 KB Ok
86 Correct 779 ms 39636 KB Ok
87 Correct 750 ms 40120 KB Ok
88 Correct 708 ms 38780 KB Ok
89 Correct 717 ms 39056 KB Ok
90 Correct 751 ms 39620 KB Ok
91 Correct 685 ms 38840 KB Ok
92 Correct 727 ms 39032 KB Ok
93 Correct 691 ms 39976 KB Ok
94 Correct 693 ms 38076 KB Ok
95 Correct 351 ms 37044 KB Ok
96 Correct 482 ms 42548 KB Ok
97 Correct 416 ms 38700 KB Ok
98 Correct 318 ms 38596 KB Ok
99 Correct 388 ms 37184 KB Ok
100 Correct 399 ms 37048 KB Ok
101 Correct 371 ms 40892 KB Ok
102 Correct 448 ms 38596 KB Ok
103 Correct 430 ms 39300 KB Ok
104 Correct 478 ms 42900 KB Ok
105 Correct 473 ms 42680 KB Ok
106 Correct 393 ms 41904 KB Ok
107 Correct 481 ms 41148 KB Ok
108 Correct 597 ms 41916 KB Ok
109 Correct 492 ms 42436 KB Ok
110 Execution timed out 2041 ms 55480 KB Time limit exceeded
111 Halted 0 ms 0 KB -