oj.uz

Submission #1006739

# Submission time Handle Problem Language Result Execution time Memory
1006739 2024-06-24T07:58:37 Z shenfe1 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 79988 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=1e6+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=1e6,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 216 ms 74560 KB Ok
2 Correct 228 ms 74584 KB Ok
3 Correct 186 ms 52664 KB Ok
4 Correct 189 ms 54360 KB Ok
5 Correct 194 ms 52796 KB Ok
6 Correct 200 ms 56948 KB Ok
7 Correct 190 ms 52096 KB Ok
8 Correct 222 ms 56768 KB Ok
9 Correct 192 ms 52660 KB Ok
10 Correct 204 ms 62644 KB Ok
11 Correct 188 ms 52160 KB Ok
12 Correct 193 ms 51792 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 62720 KB Ok
2 Correct 197 ms 62656 KB Ok
3 Correct 201 ms 62656 KB Ok
4 Correct 213 ms 62848 KB Ok
5 Correct 189 ms 62788 KB Ok
6 Correct 195 ms 62888 KB Ok
7 Correct 224 ms 63412 KB Ok
8 Correct 197 ms 62952 KB Ok
9 Correct 221 ms 63672 KB Ok
10 Correct 199 ms 63260 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 74432 KB Ok
2 Correct 240 ms 74432 KB Ok
3 Correct 228 ms 74420 KB Ok
4 Correct 198 ms 74556 KB Ok
5 Correct 185 ms 74432 KB Ok
6 Correct 175 ms 74420 KB Ok
7 Correct 202 ms 74428 KB Ok
8 Correct 171 ms 74424 KB Ok
9 Correct 204 ms 74496 KB Ok
10 Correct 187 ms 74424 KB Ok
11 Correct 206 ms 74548 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 62656 KB Ok
2 Correct 148 ms 54208 KB Ok
3 Correct 143 ms 52928 KB Ok
4 Correct 176 ms 52412 KB Ok
5 Correct 168 ms 52248 KB Ok
6 Correct 300 ms 62496 KB Ok
7 Correct 337 ms 67220 KB Ok
8 Correct 388 ms 65712 KB Ok
9 Correct 345 ms 66224 KB Ok
10 Correct 319 ms 60696 KB Ok
11 Correct 351 ms 66488 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 74560 KB Ok
2 Correct 228 ms 74584 KB Ok
3 Correct 186 ms 52664 KB Ok
4 Correct 189 ms 54360 KB Ok
5 Correct 194 ms 52796 KB Ok
6 Correct 200 ms 56948 KB Ok
7 Correct 190 ms 52096 KB Ok
8 Correct 222 ms 56768 KB Ok
9 Correct 192 ms 52660 KB Ok
10 Correct 204 ms 62644 KB Ok
11 Correct 188 ms 52160 KB Ok
12 Correct 193 ms 51792 KB Ok
13 Correct 103 ms 74432 KB Ok
14 Correct 240 ms 74432 KB Ok
15 Correct 228 ms 74420 KB Ok
16 Correct 198 ms 74556 KB Ok
17 Correct 185 ms 74432 KB Ok
18 Correct 175 ms 74420 KB Ok
19 Correct 202 ms 74428 KB Ok
20 Correct 171 ms 74424 KB Ok
21 Correct 204 ms 74496 KB Ok
22 Correct 187 ms 74424 KB Ok
23 Correct 206 ms 74548 KB Ok
24 Correct 204 ms 51140 KB Ok
25 Correct 207 ms 51076 KB Ok
26 Correct 204 ms 51128 KB Ok
27 Correct 239 ms 51160 KB Ok
28 Correct 197 ms 51380 KB Ok
29 Correct 184 ms 51120 KB Ok
30 Correct 200 ms 52152 KB Ok
31 Correct 206 ms 51132 KB Ok
32 Correct 215 ms 51156 KB Ok
33 Correct 211 ms 51180 KB Ok
34 Correct 280 ms 51380 KB Ok
35 Correct 312 ms 51392 KB Ok
36 Correct 348 ms 51388 KB Ok
37 Correct 312 ms 51276 KB Ok
38 Correct 277 ms 51292 KB Ok
39 Correct 358 ms 51620 KB Ok
40 Correct 291 ms 51380 KB Ok
41 Correct 295 ms 51380 KB Ok
42 Correct 301 ms 51368 KB Ok
43 Correct 307 ms 51340 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 74560 KB Ok
2 Correct 228 ms 74584 KB Ok
3 Correct 186 ms 52664 KB Ok
4 Correct 189 ms 54360 KB Ok
5 Correct 194 ms 52796 KB Ok
6 Correct 200 ms 56948 KB Ok
7 Correct 190 ms 52096 KB Ok
8 Correct 222 ms 56768 KB Ok
9 Correct 192 ms 52660 KB Ok
10 Correct 204 ms 62644 KB Ok
11 Correct 188 ms 52160 KB Ok
12 Correct 193 ms 51792 KB Ok
13 Correct 228 ms 62720 KB Ok
14 Correct 197 ms 62656 KB Ok
15 Correct 201 ms 62656 KB Ok
16 Correct 213 ms 62848 KB Ok
17 Correct 189 ms 62788 KB Ok
18 Correct 195 ms 62888 KB Ok
19 Correct 224 ms 63412 KB Ok
20 Correct 197 ms 62952 KB Ok
21 Correct 221 ms 63672 KB Ok
22 Correct 199 ms 63260 KB Ok
23 Correct 103 ms 74432 KB Ok
24 Correct 240 ms 74432 KB Ok
25 Correct 228 ms 74420 KB Ok
26 Correct 198 ms 74556 KB Ok
27 Correct 185 ms 74432 KB Ok
28 Correct 175 ms 74420 KB Ok
29 Correct 202 ms 74428 KB Ok
30 Correct 171 ms 74424 KB Ok
31 Correct 204 ms 74496 KB Ok
32 Correct 187 ms 74424 KB Ok
33 Correct 206 ms 74548 KB Ok
34 Correct 204 ms 51140 KB Ok
35 Correct 207 ms 51076 KB Ok
36 Correct 204 ms 51128 KB Ok
37 Correct 239 ms 51160 KB Ok
38 Correct 197 ms 51380 KB Ok
39 Correct 184 ms 51120 KB Ok
40 Correct 200 ms 52152 KB Ok
41 Correct 206 ms 51132 KB Ok
42 Correct 215 ms 51156 KB Ok
43 Correct 211 ms 51180 KB Ok
44 Correct 280 ms 51380 KB Ok
45 Correct 312 ms 51392 KB Ok
46 Correct 348 ms 51388 KB Ok
47 Correct 312 ms 51276 KB Ok
48 Correct 277 ms 51292 KB Ok
49 Correct 358 ms 51620 KB Ok
50 Correct 291 ms 51380 KB Ok
51 Correct 295 ms 51380 KB Ok
52 Correct 301 ms 51368 KB Ok
53 Correct 307 ms 51340 KB Ok
54 Correct 296 ms 53720 KB Ok
55 Correct 275 ms 53944 KB Ok
56 Correct 310 ms 54964 KB Ok
57 Correct 225 ms 53184 KB Ok
58 Correct 284 ms 53524 KB Ok
59 Correct 246 ms 58388 KB Ok
60 Correct 252 ms 56772 KB Ok
61 Correct 229 ms 53176 KB Ok
62 Correct 285 ms 53580 KB Ok
63 Correct 260 ms 53432 KB Ok
64 Correct 331 ms 53944 KB Ok
65 Correct 291 ms 53696 KB Ok
66 Correct 251 ms 53676 KB Ok
67 Correct 289 ms 53556 KB Ok
68 Correct 293 ms 53692 KB Ok
69 Correct 1033 ms 63668 KB Ok
70 Correct 1109 ms 63928 KB Ok
71 Correct 1130 ms 63580 KB Ok
72 Correct 988 ms 62976 KB Ok
73 Correct 1065 ms 63212 KB Ok
74 Correct 1155 ms 63056 KB Ok
75 Correct 1072 ms 63920 KB Ok
76 Correct 1024 ms 64436 KB Ok
77 Correct 1096 ms 64032 KB Ok
78 Correct 1062 ms 64652 KB Ok
79 Correct 1076 ms 63264 KB Ok
80 Correct 1008 ms 64420 KB Ok
81 Correct 1101 ms 64696 KB Ok
82 Correct 1106 ms 63916 KB Ok
83 Correct 1097 ms 63408 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 74560 KB Ok
2 Correct 228 ms 74584 KB Ok
3 Correct 186 ms 52664 KB Ok
4 Correct 189 ms 54360 KB Ok
5 Correct 194 ms 52796 KB Ok
6 Correct 200 ms 56948 KB Ok
7 Correct 190 ms 52096 KB Ok
8 Correct 222 ms 56768 KB Ok
9 Correct 192 ms 52660 KB Ok
10 Correct 204 ms 62644 KB Ok
11 Correct 188 ms 52160 KB Ok
12 Correct 193 ms 51792 KB Ok
13 Correct 228 ms 62720 KB Ok
14 Correct 197 ms 62656 KB Ok
15 Correct 201 ms 62656 KB Ok
16 Correct 213 ms 62848 KB Ok
17 Correct 189 ms 62788 KB Ok
18 Correct 195 ms 62888 KB Ok
19 Correct 224 ms 63412 KB Ok
20 Correct 197 ms 62952 KB Ok
21 Correct 221 ms 63672 KB Ok
22 Correct 199 ms 63260 KB Ok
23 Correct 103 ms 74432 KB Ok
24 Correct 240 ms 74432 KB Ok
25 Correct 228 ms 74420 KB Ok
26 Correct 198 ms 74556 KB Ok
27 Correct 185 ms 74432 KB Ok
28 Correct 175 ms 74420 KB Ok
29 Correct 202 ms 74428 KB Ok
30 Correct 171 ms 74424 KB Ok
31 Correct 204 ms 74496 KB Ok
32 Correct 187 ms 74424 KB Ok
33 Correct 206 ms 74548 KB Ok
34 Correct 178 ms 62656 KB Ok
35 Correct 148 ms 54208 KB Ok
36 Correct 143 ms 52928 KB Ok
37 Correct 176 ms 52412 KB Ok
38 Correct 168 ms 52248 KB Ok
39 Correct 300 ms 62496 KB Ok
40 Correct 337 ms 67220 KB Ok
41 Correct 388 ms 65712 KB Ok
42 Correct 345 ms 66224 KB Ok
43 Correct 319 ms 60696 KB Ok
44 Correct 351 ms 66488 KB Ok
45 Correct 204 ms 51140 KB Ok
46 Correct 207 ms 51076 KB Ok
47 Correct 204 ms 51128 KB Ok
48 Correct 239 ms 51160 KB Ok
49 Correct 197 ms 51380 KB Ok
50 Correct 184 ms 51120 KB Ok
51 Correct 200 ms 52152 KB Ok
52 Correct 206 ms 51132 KB Ok
53 Correct 215 ms 51156 KB Ok
54 Correct 211 ms 51180 KB Ok
55 Correct 280 ms 51380 KB Ok
56 Correct 312 ms 51392 KB Ok
57 Correct 348 ms 51388 KB Ok
58 Correct 312 ms 51276 KB Ok
59 Correct 277 ms 51292 KB Ok
60 Correct 358 ms 51620 KB Ok
61 Correct 291 ms 51380 KB Ok
62 Correct 295 ms 51380 KB Ok
63 Correct 301 ms 51368 KB Ok
64 Correct 307 ms 51340 KB Ok
65 Correct 296 ms 53720 KB Ok
66 Correct 275 ms 53944 KB Ok
67 Correct 310 ms 54964 KB Ok
68 Correct 225 ms 53184 KB Ok
69 Correct 284 ms 53524 KB Ok
70 Correct 246 ms 58388 KB Ok
71 Correct 252 ms 56772 KB Ok
72 Correct 229 ms 53176 KB Ok
73 Correct 285 ms 53580 KB Ok
74 Correct 260 ms 53432 KB Ok
75 Correct 331 ms 53944 KB Ok
76 Correct 291 ms 53696 KB Ok
77 Correct 251 ms 53676 KB Ok
78 Correct 289 ms 53556 KB Ok
79 Correct 293 ms 53692 KB Ok
80 Correct 1033 ms 63668 KB Ok
81 Correct 1109 ms 63928 KB Ok
82 Correct 1130 ms 63580 KB Ok
83 Correct 988 ms 62976 KB Ok
84 Correct 1065 ms 63212 KB Ok
85 Correct 1155 ms 63056 KB Ok
86 Correct 1072 ms 63920 KB Ok
87 Correct 1024 ms 64436 KB Ok
88 Correct 1096 ms 64032 KB Ok
89 Correct 1062 ms 64652 KB Ok
90 Correct 1076 ms 63264 KB Ok
91 Correct 1008 ms 64420 KB Ok
92 Correct 1101 ms 64696 KB Ok
93 Correct 1106 ms 63916 KB Ok
94 Correct 1097 ms 63408 KB Ok
95 Correct 451 ms 62468 KB Ok
96 Correct 587 ms 65328 KB Ok
97 Correct 534 ms 63672 KB Ok
98 Correct 421 ms 62904 KB Ok
99 Correct 480 ms 62756 KB Ok
100 Correct 545 ms 61624 KB Ok
101 Correct 486 ms 62740 KB Ok
102 Correct 534 ms 64564 KB Ok
103 Correct 529 ms 62900 KB Ok
104 Correct 569 ms 64688 KB Ok
105 Correct 619 ms 64440 KB Ok
106 Correct 497 ms 64172 KB Ok
107 Correct 511 ms 63412 KB Ok
108 Correct 637 ms 62644 KB Ok
109 Correct 571 ms 65156 KB Ok
110 Execution timed out 2033 ms 79988 KB Time limit exceeded
111 Halted 0 ms 0 KB -