oj.uz

답안 #1006617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006617 2024-06-24T05:44:07 Z shenfe1 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 74668 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=1,r=1e6,res=0;
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 74432 KB Ok
2 Correct 257 ms 74432 KB Ok
3 Correct 226 ms 52664 KB Ok
4 Correct 220 ms 54452 KB Ok
5 Correct 211 ms 52664 KB Ok
6 Correct 235 ms 56944 KB Ok
7 Correct 228 ms 52160 KB Ok
8 Correct 209 ms 56768 KB Ok
9 Correct 202 ms 52668 KB Ok
10 Correct 237 ms 62660 KB Ok
11 Correct 216 ms 52160 KB Ok
12 Correct 216 ms 51640 KB Ok

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 62684 KB Ok
2 Correct 211 ms 62656 KB Ok
3 Correct 207 ms 62768 KB Ok
4 Correct 217 ms 62656 KB Ok
5 Correct 183 ms 63032 KB Ok
6 Correct 205 ms 62892 KB Ok
7 Correct 207 ms 63416 KB Ok
8 Correct 193 ms 62968 KB Ok
9 Correct 268 ms 63492 KB Ok
10 Correct 207 ms 63164 KB Ok

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 74548 KB Ok
2 Correct 273 ms 74428 KB Ok
3 Correct 211 ms 74420 KB Ok
4 Correct 213 ms 74420 KB Ok
5 Correct 217 ms 74428 KB Ok
6 Correct 191 ms 74668 KB Ok
7 Correct 200 ms 74432 KB Ok
8 Correct 181 ms 74420 KB Ok
9 Correct 209 ms 74420 KB Ok
10 Correct 196 ms 74432 KB Ok
11 Correct 197 ms 74420 KB Ok

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 62684 KB Ok
2 Correct 172 ms 54472 KB Ok
3 Correct 180 ms 53064 KB Ok
4 Correct 176 ms 52412 KB Ok
5 Correct 193 ms 52156 KB Ok
6 Correct 331 ms 60852 KB Ok
7 Correct 346 ms 62256 KB Ok
8 Correct 373 ms 63932 KB Ok
9 Correct 376 ms 63432 KB Ok
10 Correct 323 ms 56760 KB Ok
11 Correct 372 ms 63676 KB Ok

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 74432 KB Ok
2 Correct 257 ms 74432 KB Ok
3 Correct 226 ms 52664 KB Ok
4 Correct 220 ms 54452 KB Ok
5 Correct 211 ms 52664 KB Ok
6 Correct 235 ms 56944 KB Ok
7 Correct 228 ms 52160 KB Ok
8 Correct 209 ms 56768 KB Ok
9 Correct 202 ms 52668 KB Ok
10 Correct 237 ms 62660 KB Ok
11 Correct 216 ms 52160 KB Ok
12 Correct 216 ms 51640 KB Ok
13 Correct 107 ms 74548 KB Ok
14 Correct 273 ms 74428 KB Ok
15 Correct 211 ms 74420 KB Ok
16 Correct 213 ms 74420 KB Ok
17 Correct 217 ms 74428 KB Ok
18 Correct 191 ms 74668 KB Ok
19 Correct 200 ms 74432 KB Ok
20 Correct 181 ms 74420 KB Ok
21 Correct 209 ms 74420 KB Ok
22 Correct 196 ms 74432 KB Ok
23 Correct 197 ms 74420 KB Ok
24 Correct 215 ms 51200 KB Ok
25 Correct 246 ms 51376 KB Ok
26 Correct 257 ms 51128 KB Ok
27 Correct 273 ms 51132 KB Ok
28 Correct 252 ms 51380 KB Ok
29 Correct 220 ms 51144 KB Ok
30 Correct 211 ms 52148 KB Ok
31 Correct 263 ms 51124 KB Ok
32 Correct 253 ms 51132 KB Ok
33 Correct 263 ms 51140 KB Ok
34 Correct 430 ms 51636 KB Ok
35 Correct 411 ms 51384 KB Ok
36 Correct 385 ms 51384 KB Ok
37 Correct 400 ms 51384 KB Ok
38 Correct 383 ms 51384 KB Ok
39 Correct 424 ms 51384 KB Ok
40 Correct 436 ms 51432 KB Ok
41 Correct 451 ms 51412 KB Ok
42 Correct 424 ms 51384 KB Ok
43 Correct 433 ms 51384 KB Ok

Subtask #6
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 74432 KB Ok
2 Correct 257 ms 74432 KB Ok
3 Correct 226 ms 52664 KB Ok
4 Correct 220 ms 54452 KB Ok
5 Correct 211 ms 52664 KB Ok
6 Correct 235 ms 56944 KB Ok
7 Correct 228 ms 52160 KB Ok
8 Correct 209 ms 56768 KB Ok
9 Correct 202 ms 52668 KB Ok
10 Correct 237 ms 62660 KB Ok
11 Correct 216 ms 52160 KB Ok
12 Correct 216 ms 51640 KB Ok
13 Correct 207 ms 62684 KB Ok
14 Correct 211 ms 62656 KB Ok
15 Correct 207 ms 62768 KB Ok
16 Correct 217 ms 62656 KB Ok
17 Correct 183 ms 63032 KB Ok
18 Correct 205 ms 62892 KB Ok
19 Correct 207 ms 63416 KB Ok
20 Correct 193 ms 62968 KB Ok
21 Correct 268 ms 63492 KB Ok
22 Correct 207 ms 63164 KB Ok
23 Correct 107 ms 74548 KB Ok
24 Correct 273 ms 74428 KB Ok
25 Correct 211 ms 74420 KB Ok
26 Correct 213 ms 74420 KB Ok
27 Correct 217 ms 74428 KB Ok
28 Correct 191 ms 74668 KB Ok
29 Correct 200 ms 74432 KB Ok
30 Correct 181 ms 74420 KB Ok
31 Correct 209 ms 74420 KB Ok
32 Correct 196 ms 74432 KB Ok
33 Correct 197 ms 74420 KB Ok
34 Correct 215 ms 51200 KB Ok
35 Correct 246 ms 51376 KB Ok
36 Correct 257 ms 51128 KB Ok
37 Correct 273 ms 51132 KB Ok
38 Correct 252 ms 51380 KB Ok
39 Correct 220 ms 51144 KB Ok
40 Correct 211 ms 52148 KB Ok
41 Correct 263 ms 51124 KB Ok
42 Correct 253 ms 51132 KB Ok
43 Correct 263 ms 51140 KB Ok
44 Correct 430 ms 51636 KB Ok
45 Correct 411 ms 51384 KB Ok
46 Correct 385 ms 51384 KB Ok
47 Correct 400 ms 51384 KB Ok
48 Correct 383 ms 51384 KB Ok
49 Correct 424 ms 51384 KB Ok
50 Correct 436 ms 51432 KB Ok
51 Correct 451 ms 51412 KB Ok
52 Correct 424 ms 51384 KB Ok
53 Correct 433 ms 51384 KB Ok
54 Correct 329 ms 52996 KB Ok
55 Correct 320 ms 53176 KB Ok
56 Correct 307 ms 53444 KB Ok
57 Correct 264 ms 52408 KB Ok
58 Correct 288 ms 52664 KB Ok
59 Correct 272 ms 52924 KB Ok
60 Correct 263 ms 52416 KB Ok
61 Correct 258 ms 52496 KB Ok
62 Correct 313 ms 53104 KB Ok
63 Correct 267 ms 52532 KB Ok
64 Correct 329 ms 53180 KB Ok
65 Correct 299 ms 52920 KB Ok
66 Correct 307 ms 52668 KB Ok
67 Correct 297 ms 52664 KB Ok
68 Correct 327 ms 52924 KB Ok
69 Correct 1299 ms 61780 KB Ok
70 Correct 1280 ms 62572 KB Ok
71 Correct 1364 ms 61780 KB Ok
72 Correct 1074 ms 61668 KB Ok
73 Correct 1088 ms 61584 KB Ok
74 Correct 1024 ms 61548 KB Ok
75 Correct 1064 ms 61624 KB Ok
76 Correct 1169 ms 61956 KB Ok
77 Correct 1086 ms 61368 KB Ok
78 Correct 1004 ms 61624 KB Ok
79 Correct 1058 ms 62140 KB Ok
80 Correct 957 ms 61880 KB Ok
81 Correct 1078 ms 61880 KB Ok
82 Correct 1147 ms 62060 KB Ok
83 Correct 1035 ms 61368 KB Ok

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 74432 KB Ok
2 Correct 257 ms 74432 KB Ok
3 Correct 226 ms 52664 KB Ok
4 Correct 220 ms 54452 KB Ok
5 Correct 211 ms 52664 KB Ok
6 Correct 235 ms 56944 KB Ok
7 Correct 228 ms 52160 KB Ok
8 Correct 209 ms 56768 KB Ok
9 Correct 202 ms 52668 KB Ok
10 Correct 237 ms 62660 KB Ok
11 Correct 216 ms 52160 KB Ok
12 Correct 216 ms 51640 KB Ok
13 Correct 207 ms 62684 KB Ok
14 Correct 211 ms 62656 KB Ok
15 Correct 207 ms 62768 KB Ok
16 Correct 217 ms 62656 KB Ok
17 Correct 183 ms 63032 KB Ok
18 Correct 205 ms 62892 KB Ok
19 Correct 207 ms 63416 KB Ok
20 Correct 193 ms 62968 KB Ok
21 Correct 268 ms 63492 KB Ok
22 Correct 207 ms 63164 KB Ok
23 Correct 107 ms 74548 KB Ok
24 Correct 273 ms 74428 KB Ok
25 Correct 211 ms 74420 KB Ok
26 Correct 213 ms 74420 KB Ok
27 Correct 217 ms 74428 KB Ok
28 Correct 191 ms 74668 KB Ok
29 Correct 200 ms 74432 KB Ok
30 Correct 181 ms 74420 KB Ok
31 Correct 209 ms 74420 KB Ok
32 Correct 196 ms 74432 KB Ok
33 Correct 197 ms 74420 KB Ok
34 Correct 163 ms 62684 KB Ok
35 Correct 172 ms 54472 KB Ok
36 Correct 180 ms 53064 KB Ok
37 Correct 176 ms 52412 KB Ok
38 Correct 193 ms 52156 KB Ok
39 Correct 331 ms 60852 KB Ok
40 Correct 346 ms 62256 KB Ok
41 Correct 373 ms 63932 KB Ok
42 Correct 376 ms 63432 KB Ok
43 Correct 323 ms 56760 KB Ok
44 Correct 372 ms 63676 KB Ok
45 Correct 215 ms 51200 KB Ok
46 Correct 246 ms 51376 KB Ok
47 Correct 257 ms 51128 KB Ok
48 Correct 273 ms 51132 KB Ok
49 Correct 252 ms 51380 KB Ok
50 Correct 220 ms 51144 KB Ok
51 Correct 211 ms 52148 KB Ok
52 Correct 263 ms 51124 KB Ok
53 Correct 253 ms 51132 KB Ok
54 Correct 263 ms 51140 KB Ok
55 Correct 430 ms 51636 KB Ok
56 Correct 411 ms 51384 KB Ok
57 Correct 385 ms 51384 KB Ok
58 Correct 400 ms 51384 KB Ok
59 Correct 383 ms 51384 KB Ok
60 Correct 424 ms 51384 KB Ok
61 Correct 436 ms 51432 KB Ok
62 Correct 451 ms 51412 KB Ok
63 Correct 424 ms 51384 KB Ok
64 Correct 433 ms 51384 KB Ok
65 Correct 329 ms 52996 KB Ok
66 Correct 320 ms 53176 KB Ok
67 Correct 307 ms 53444 KB Ok
68 Correct 264 ms 52408 KB Ok
69 Correct 288 ms 52664 KB Ok
70 Correct 272 ms 52924 KB Ok
71 Correct 263 ms 52416 KB Ok
72 Correct 258 ms 52496 KB Ok
73 Correct 313 ms 53104 KB Ok
74 Correct 267 ms 52532 KB Ok
75 Correct 329 ms 53180 KB Ok
76 Correct 299 ms 52920 KB Ok
77 Correct 307 ms 52668 KB Ok
78 Correct 297 ms 52664 KB Ok
79 Correct 327 ms 52924 KB Ok
80 Correct 1299 ms 61780 KB Ok
81 Correct 1280 ms 62572 KB Ok
82 Correct 1364 ms 61780 KB Ok
83 Correct 1074 ms 61668 KB Ok
84 Correct 1088 ms 61584 KB Ok
85 Correct 1024 ms 61548 KB Ok
86 Correct 1064 ms 61624 KB Ok
87 Correct 1169 ms 61956 KB Ok
88 Correct 1086 ms 61368 KB Ok
89 Correct 1004 ms 61624 KB Ok
90 Correct 1058 ms 62140 KB Ok
91 Correct 957 ms 61880 KB Ok
92 Correct 1078 ms 61880 KB Ok
93 Correct 1147 ms 62060 KB Ok
94 Correct 1035 ms 61368 KB Ok
95 Correct 432 ms 58556 KB Ok
96 Correct 532 ms 60344 KB Ok
97 Correct 500 ms 59316 KB Ok
98 Correct 354 ms 58308 KB Ok
99 Correct 509 ms 58604 KB Ok
100 Correct 534 ms 58808 KB Ok
101 Correct 448 ms 58556 KB Ok
102 Correct 518 ms 59324 KB Ok
103 Correct 562 ms 59576 KB Ok
104 Correct 564 ms 60088 KB Ok
105 Correct 589 ms 59860 KB Ok
106 Correct 430 ms 59396 KB Ok
107 Correct 526 ms 59064 KB Ok
108 Correct 579 ms 59576 KB Ok
109 Correct 535 ms 60088 KB Ok
110 Execution timed out 2037 ms 72572 KB Time limit exceeded
111 Halted 0 ms 0 KB -