oj.uz

Submission #1006754

# Submission time Handle Problem Language Result Execution time Memory
1006754 2024-06-24T08:20:24 Z shenfe1 Nice sequence (IZhO18_sequence) C++17
100 / 100
 983 ms 63260 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,R;
int p[MAX];
int use[MAX];
bool ok;
vector<int> g[MAX];
vector<int> top;

void dfs(int v){
  // cerr<<v<<'\n';
  assert(0<=v&&v<=R);
  use[v]=1;
  if(v-m>=0&&!use[v-m]){
    dfs(v-m);
  }
  else if(v-m>=0&&use[v-m]==1){
    ok=0;
  }
  if(v+n<=R&&!use[v+n]){
    dfs(v+n);
  }
  else if(v+n<=R&&use[v+n]==1){
    ok=0;
  }
  top.pb(v);
  use[v]=2;
}

bool check(int mid){
  R=mid;
  ok=1;
  top.clear();
  mem(use,0);
  // cerr<<mid<<" "<<R<<'\n';
  for(int i=0;i<=mid;i++){
    if(!use[i]){
      dfs(i);
    }
  }
  if(!ok)return 0;
  return 1;
}

void solve(){
  cin>>n>>m;
  bool isRev=0;
  if(n<m){
    isRev=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=0;i<=res;i++){
    p[top[i]]=i;
  }
  for(int i=1;i<=res;i++)p[i]-=p[0];
  p[0]=0;
  for(int i=res;i>=1;i--)p[i]-=p[i-1];
  // cout<<isRev<<"\n";
  if(isRev)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 63 ms 26836 KB Ok
2 Correct 55 ms 26840 KB Ok
3 Correct 51 ms 19656 KB Ok
4 Correct 51 ms 20164 KB Ok
5 Correct 54 ms 19668 KB Ok
6 Correct 52 ms 20944 KB Ok
7 Correct 52 ms 19416 KB Ok
8 Correct 48 ms 21208 KB Ok
9 Correct 49 ms 19664 KB Ok
10 Correct 50 ms 22876 KB Ok
11 Correct 55 ms 19412 KB Ok
12 Correct 46 ms 19380 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 26832 KB Ok
2 Correct 65 ms 26836 KB Ok
3 Correct 66 ms 26836 KB Ok
4 Correct 63 ms 26836 KB Ok
5 Correct 59 ms 26836 KB Ok
6 Correct 61 ms 26840 KB Ok
7 Correct 66 ms 27196 KB Ok
8 Correct 59 ms 26836 KB Ok
9 Correct 78 ms 27292 KB Ok
10 Correct 65 ms 26800 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26840 KB Ok
2 Correct 64 ms 26836 KB Ok
3 Correct 72 ms 26816 KB Ok
4 Correct 71 ms 26836 KB Ok
5 Correct 67 ms 26840 KB Ok
6 Correct 68 ms 26836 KB Ok
7 Correct 69 ms 27056 KB Ok
8 Correct 71 ms 26900 KB Ok
9 Correct 67 ms 26828 KB Ok
10 Correct 68 ms 26836 KB Ok
11 Correct 77 ms 26836 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 26840 KB Ok
2 Correct 76 ms 26840 KB Ok
3 Correct 64 ms 26836 KB Ok
4 Correct 84 ms 26836 KB Ok
5 Correct 68 ms 26836 KB Ok
6 Correct 189 ms 35268 KB Ok
7 Correct 198 ms 33168 KB Ok
8 Correct 279 ms 37288 KB Ok
9 Correct 214 ms 35004 KB Ok
10 Correct 173 ms 32460 KB Ok
11 Correct 234 ms 34240 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 26836 KB Ok
2 Correct 55 ms 26840 KB Ok
3 Correct 51 ms 19656 KB Ok
4 Correct 51 ms 20164 KB Ok
5 Correct 54 ms 19668 KB Ok
6 Correct 52 ms 20944 KB Ok
7 Correct 52 ms 19416 KB Ok
8 Correct 48 ms 21208 KB Ok
9 Correct 49 ms 19664 KB Ok
10 Correct 50 ms 22876 KB Ok
11 Correct 55 ms 19412 KB Ok
12 Correct 46 ms 19380 KB Ok
13 Correct 29 ms 26840 KB Ok
14 Correct 64 ms 26836 KB Ok
15 Correct 72 ms 26816 KB Ok
16 Correct 71 ms 26836 KB Ok
17 Correct 67 ms 26840 KB Ok
18 Correct 68 ms 26836 KB Ok
19 Correct 69 ms 27056 KB Ok
20 Correct 71 ms 26900 KB Ok
21 Correct 67 ms 26828 KB Ok
22 Correct 68 ms 26836 KB Ok
23 Correct 77 ms 26836 KB Ok
24 Correct 56 ms 19156 KB Ok
25 Correct 53 ms 19160 KB Ok
26 Correct 50 ms 19668 KB Ok
27 Correct 58 ms 19668 KB Ok
28 Correct 54 ms 19412 KB Ok
29 Correct 53 ms 21704 KB Ok
30 Correct 53 ms 19512 KB Ok
31 Correct 50 ms 19160 KB Ok
32 Correct 49 ms 19160 KB Ok
33 Correct 53 ms 19400 KB Ok
34 Correct 66 ms 26836 KB Ok
35 Correct 68 ms 26980 KB Ok
36 Correct 76 ms 27076 KB Ok
37 Correct 72 ms 27092 KB Ok
38 Correct 69 ms 27076 KB Ok
39 Correct 72 ms 27076 KB Ok
40 Correct 67 ms 27068 KB Ok
41 Correct 70 ms 27080 KB Ok
42 Correct 75 ms 27092 KB Ok
43 Correct 68 ms 27116 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 26836 KB Ok
2 Correct 55 ms 26840 KB Ok
3 Correct 51 ms 19656 KB Ok
4 Correct 51 ms 20164 KB Ok
5 Correct 54 ms 19668 KB Ok
6 Correct 52 ms 20944 KB Ok
7 Correct 52 ms 19416 KB Ok
8 Correct 48 ms 21208 KB Ok
9 Correct 49 ms 19664 KB Ok
10 Correct 50 ms 22876 KB Ok
11 Correct 55 ms 19412 KB Ok
12 Correct 46 ms 19380 KB Ok
13 Correct 76 ms 26832 KB Ok
14 Correct 65 ms 26836 KB Ok
15 Correct 66 ms 26836 KB Ok
16 Correct 63 ms 26836 KB Ok
17 Correct 59 ms 26836 KB Ok
18 Correct 61 ms 26840 KB Ok
19 Correct 66 ms 27196 KB Ok
20 Correct 59 ms 26836 KB Ok
21 Correct 78 ms 27292 KB Ok
22 Correct 65 ms 26800 KB Ok
23 Correct 29 ms 26840 KB Ok
24 Correct 64 ms 26836 KB Ok
25 Correct 72 ms 26816 KB Ok
26 Correct 71 ms 26836 KB Ok
27 Correct 67 ms 26840 KB Ok
28 Correct 68 ms 26836 KB Ok
29 Correct 69 ms 27056 KB Ok
30 Correct 71 ms 26900 KB Ok
31 Correct 67 ms 26828 KB Ok
32 Correct 68 ms 26836 KB Ok
33 Correct 77 ms 26836 KB Ok
34 Correct 56 ms 19156 KB Ok
35 Correct 53 ms 19160 KB Ok
36 Correct 50 ms 19668 KB Ok
37 Correct 58 ms 19668 KB Ok
38 Correct 54 ms 19412 KB Ok
39 Correct 53 ms 21704 KB Ok
40 Correct 53 ms 19512 KB Ok
41 Correct 50 ms 19160 KB Ok
42 Correct 49 ms 19160 KB Ok
43 Correct 53 ms 19400 KB Ok
44 Correct 66 ms 26836 KB Ok
45 Correct 68 ms 26980 KB Ok
46 Correct 76 ms 27076 KB Ok
47 Correct 72 ms 27092 KB Ok
48 Correct 69 ms 27076 KB Ok
49 Correct 72 ms 27076 KB Ok
50 Correct 67 ms 27068 KB Ok
51 Correct 70 ms 27080 KB Ok
52 Correct 75 ms 27092 KB Ok
53 Correct 68 ms 27116 KB Ok
54 Correct 103 ms 22480 KB Ok
55 Correct 119 ms 22204 KB Ok
56 Correct 109 ms 23252 KB Ok
57 Correct 99 ms 22996 KB Ok
58 Correct 113 ms 21948 KB Ok
59 Correct 112 ms 22228 KB Ok
60 Correct 111 ms 21532 KB Ok
61 Correct 100 ms 22996 KB Ok
62 Correct 140 ms 22716 KB Ok
63 Correct 97 ms 22480 KB Ok
64 Correct 109 ms 23492 KB Ok
65 Correct 120 ms 22740 KB Ok
66 Correct 99 ms 22228 KB Ok
67 Correct 134 ms 22228 KB Ok
68 Correct 100 ms 22296 KB Ok
69 Correct 266 ms 33216 KB Ok
70 Correct 246 ms 32704 KB Ok
71 Correct 255 ms 33560 KB Ok
72 Correct 235 ms 33316 KB Ok
73 Correct 227 ms 32028 KB Ok
74 Correct 244 ms 33324 KB Ok
75 Correct 266 ms 32704 KB Ok
76 Correct 246 ms 32328 KB Ok
77 Correct 264 ms 31480 KB Ok
78 Correct 257 ms 31748 KB Ok
79 Correct 254 ms 32444 KB Ok
80 Correct 249 ms 33368 KB Ok
81 Correct 236 ms 33212 KB Ok
82 Correct 244 ms 32724 KB Ok
83 Correct 282 ms 33608 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 26836 KB Ok
2 Correct 55 ms 26840 KB Ok
3 Correct 51 ms 19656 KB Ok
4 Correct 51 ms 20164 KB Ok
5 Correct 54 ms 19668 KB Ok
6 Correct 52 ms 20944 KB Ok
7 Correct 52 ms 19416 KB Ok
8 Correct 48 ms 21208 KB Ok
9 Correct 49 ms 19664 KB Ok
10 Correct 50 ms 22876 KB Ok
11 Correct 55 ms 19412 KB Ok
12 Correct 46 ms 19380 KB Ok
13 Correct 76 ms 26832 KB Ok
14 Correct 65 ms 26836 KB Ok
15 Correct 66 ms 26836 KB Ok
16 Correct 63 ms 26836 KB Ok
17 Correct 59 ms 26836 KB Ok
18 Correct 61 ms 26840 KB Ok
19 Correct 66 ms 27196 KB Ok
20 Correct 59 ms 26836 KB Ok
21 Correct 78 ms 27292 KB Ok
22 Correct 65 ms 26800 KB Ok
23 Correct 29 ms 26840 KB Ok
24 Correct 64 ms 26836 KB Ok
25 Correct 72 ms 26816 KB Ok
26 Correct 71 ms 26836 KB Ok
27 Correct 67 ms 26840 KB Ok
28 Correct 68 ms 26836 KB Ok
29 Correct 69 ms 27056 KB Ok
30 Correct 71 ms 26900 KB Ok
31 Correct 67 ms 26828 KB Ok
32 Correct 68 ms 26836 KB Ok
33 Correct 77 ms 26836 KB Ok
34 Correct 88 ms 26840 KB Ok
35 Correct 76 ms 26840 KB Ok
36 Correct 64 ms 26836 KB Ok
37 Correct 84 ms 26836 KB Ok
38 Correct 68 ms 26836 KB Ok
39 Correct 189 ms 35268 KB Ok
40 Correct 198 ms 33168 KB Ok
41 Correct 279 ms 37288 KB Ok
42 Correct 214 ms 35004 KB Ok
43 Correct 173 ms 32460 KB Ok
44 Correct 234 ms 34240 KB Ok
45 Correct 56 ms 19156 KB Ok
46 Correct 53 ms 19160 KB Ok
47 Correct 50 ms 19668 KB Ok
48 Correct 58 ms 19668 KB Ok
49 Correct 54 ms 19412 KB Ok
50 Correct 53 ms 21704 KB Ok
51 Correct 53 ms 19512 KB Ok
52 Correct 50 ms 19160 KB Ok
53 Correct 49 ms 19160 KB Ok
54 Correct 53 ms 19400 KB Ok
55 Correct 66 ms 26836 KB Ok
56 Correct 68 ms 26980 KB Ok
57 Correct 76 ms 27076 KB Ok
58 Correct 72 ms 27092 KB Ok
59 Correct 69 ms 27076 KB Ok
60 Correct 72 ms 27076 KB Ok
61 Correct 67 ms 27068 KB Ok
62 Correct 70 ms 27080 KB Ok
63 Correct 75 ms 27092 KB Ok
64 Correct 68 ms 27116 KB Ok
65 Correct 103 ms 22480 KB Ok
66 Correct 119 ms 22204 KB Ok
67 Correct 109 ms 23252 KB Ok
68 Correct 99 ms 22996 KB Ok
69 Correct 113 ms 21948 KB Ok
70 Correct 112 ms 22228 KB Ok
71 Correct 111 ms 21532 KB Ok
72 Correct 100 ms 22996 KB Ok
73 Correct 140 ms 22716 KB Ok
74 Correct 97 ms 22480 KB Ok
75 Correct 109 ms 23492 KB Ok
76 Correct 120 ms 22740 KB Ok
77 Correct 99 ms 22228 KB Ok
78 Correct 134 ms 22228 KB Ok
79 Correct 100 ms 22296 KB Ok
80 Correct 266 ms 33216 KB Ok
81 Correct 246 ms 32704 KB Ok
82 Correct 255 ms 33560 KB Ok
83 Correct 235 ms 33316 KB Ok
84 Correct 227 ms 32028 KB Ok
85 Correct 244 ms 33324 KB Ok
86 Correct 266 ms 32704 KB Ok
87 Correct 246 ms 32328 KB Ok
88 Correct 264 ms 31480 KB Ok
89 Correct 257 ms 31748 KB Ok
90 Correct 254 ms 32444 KB Ok
91 Correct 249 ms 33368 KB Ok
92 Correct 236 ms 33212 KB Ok
93 Correct 244 ms 32724 KB Ok
94 Correct 282 ms 33608 KB Ok
95 Correct 281 ms 26812 KB Ok
96 Correct 303 ms 29376 KB Ok
97 Correct 295 ms 28352 KB Ok
98 Correct 228 ms 26556 KB Ok
99 Correct 226 ms 28040 KB Ok
100 Correct 268 ms 28348 KB Ok
101 Correct 280 ms 29116 KB Ok
102 Correct 234 ms 28816 KB Ok
103 Correct 249 ms 27580 KB Ok
104 Correct 353 ms 30660 KB Ok
105 Correct 303 ms 29116 KB Ok
106 Correct 274 ms 27836 KB Ok
107 Correct 328 ms 29404 KB Ok
108 Correct 372 ms 30588 KB Ok
109 Correct 265 ms 28864 KB Ok
110 Correct 893 ms 60640 KB Ok
111 Correct 922 ms 62908 KB Ok
112 Correct 905 ms 63260 KB Ok
113 Correct 826 ms 61632 KB Ok
114 Correct 907 ms 63168 KB Ok
115 Correct 837 ms 61888 KB Ok
116 Correct 860 ms 63168 KB Ok
117 Correct 901 ms 62808 KB Ok
118 Correct 894 ms 63164 KB Ok
119 Correct 983 ms 62000 KB Ok
120 Correct 923 ms 62400 KB Ok
121 Correct 925 ms 60096 KB Ok
122 Correct 983 ms 62652 KB Ok
123 Correct 936 ms 63168 KB Ok
124 Correct 823 ms 60844 KB Ok
125 Correct 788 ms 45248 KB Ok