oj.uz

Submission #1086399

# Submission time Handle Problem Language Result Execution time Memory
1086399 2024-09-10T13:04:15 Z 8pete8 Nice sequence (IZhO18_sequence) C++17
76 / 100
 143 ms 28496 KB 
#include<stdio.h>
#include <stdlib.h>
#define int long long
int compare(const void* a, const void* b){
   return (*(int*)a - *(int*)b);
}
const int mx=1e9,mxn=2e5;
int k=0;
int *adj[mxn+10],sz[mxn+10],vis[mxn+10],ord[mxn+10],cnt=0;
int what[mxn+10];
void ts(int cur){
    vis[cur]=1;
    for(int i=0;i<sz[cur];i++)if(!vis[adj[cur][i]])ts(adj[cur][i]);
    ord[cnt++]=cur;
}
void re(int m,int n){
    //get length
    k+=(m/n)*n;
    if(m%n)re(n,m%n);
}
void solve(){
    k=0,cnt=0;
    int n,m;scanf("%lld %lld",&n,&m);
    int mul=-1;
    if(n>m){
        n^=m,m^=n,n^=m;
        mul=1;
    }
    re(m,n);
    k--;
    for(int i=0;i<=k;i++){
        if(i-m>=0){
            adj[i] = (int *)realloc(adj[i],(sz[i] + 1)*sizeof(int));
            adj[i][sz[i]++]=i-m;
        }
        if(i-n>=0){
            adj[i-n]=(int *)realloc(adj[i-n],(sz[i-n] + 1)*sizeof(int));
            adj[i-n][sz[i-n]++]=i;
        }
    }
    //get length
    printf("%lld\n",k);
    for(int i=0;i<=k;i++)if(!vis[i])ts(i);
    for(int i=cnt;i>=0;i--)what[ord[i]]=(k-i);
    for(int i=1;i<=k;i++)printf("%lld ",mul*(what[i]-what[i-1]));
    for(int i=0;i<=k;i++){
        if(adj[i]!=NULL)free(adj[i]);
        adj[i]=NULL;
        sz[i]=what[i]=vis[i]=0;
    }
    printf("\n");
}
int32_t main(){
    int t;scanf("%lld",&t);
    while(t--)solve();
}
/*
 
+++-
 
3
3 1
2 3 
1 1

case 


 
*/

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     int n,m;scanf("%lld %lld",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int32_t main()':
sequence.cpp:54:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     int t;scanf("%lld",&t);
      |           ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 344 KB Ok
12 Correct 0 ms 348 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 0 ms 604 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 0 ms 600 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 2 ms 604 KB Ok
7 Correct 8 ms 1628 KB Ok
8 Correct 4 ms 860 KB Ok
9 Correct 9 ms 1704 KB Ok
10 Correct 5 ms 1116 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 428 KB Ok
7 Correct 1 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 344 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 75 ms 17744 KB Ok
7 Correct 66 ms 17484 KB Ok
8 Correct 119 ms 22672 KB Ok
9 Correct 97 ms 20748 KB Ok
10 Correct 54 ms 11488 KB Ok
11 Correct 89 ms 22100 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 344 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 0 ms 600 KB Ok
14 Correct 0 ms 348 KB Ok
15 Correct 0 ms 348 KB Ok
16 Correct 0 ms 348 KB Ok
17 Correct 0 ms 348 KB Ok
18 Correct 0 ms 428 KB Ok
19 Correct 1 ms 348 KB Ok
20 Correct 0 ms 348 KB Ok
21 Correct 1 ms 348 KB Ok
22 Correct 0 ms 348 KB Ok
23 Correct 0 ms 348 KB Ok
24 Correct 2 ms 2652 KB Ok
25 Correct 2 ms 2476 KB Ok
26 Correct 2 ms 2652 KB Ok
27 Correct 2 ms 2652 KB Ok
28 Correct 1 ms 2652 KB Ok
29 Correct 1 ms 2396 KB Ok
30 Correct 2 ms 2392 KB Ok
31 Correct 3 ms 2652 KB Ok
32 Correct 2 ms 2648 KB Ok
33 Correct 1 ms 2652 KB Ok
34 Correct 3 ms 2908 KB Ok
35 Correct 3 ms 2908 KB Ok
36 Correct 7 ms 2904 KB Ok
37 Correct 3 ms 2904 KB Ok
38 Correct 5 ms 2908 KB Ok
39 Correct 3 ms 2908 KB Ok
40 Correct 4 ms 2908 KB Ok
41 Correct 3 ms 2908 KB Ok
42 Correct 3 ms 3164 KB Ok
43 Correct 5 ms 2956 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 344 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 0 ms 344 KB Ok
14 Correct 0 ms 604 KB Ok
15 Correct 1 ms 348 KB Ok
16 Correct 0 ms 600 KB Ok
17 Correct 0 ms 348 KB Ok
18 Correct 2 ms 604 KB Ok
19 Correct 8 ms 1628 KB Ok
20 Correct 4 ms 860 KB Ok
21 Correct 9 ms 1704 KB Ok
22 Correct 5 ms 1116 KB Ok
23 Correct 0 ms 600 KB Ok
24 Correct 0 ms 348 KB Ok
25 Correct 0 ms 348 KB Ok
26 Correct 0 ms 348 KB Ok
27 Correct 0 ms 348 KB Ok
28 Correct 0 ms 428 KB Ok
29 Correct 1 ms 348 KB Ok
30 Correct 0 ms 348 KB Ok
31 Correct 1 ms 348 KB Ok
32 Correct 0 ms 348 KB Ok
33 Correct 0 ms 348 KB Ok
34 Correct 2 ms 2652 KB Ok
35 Correct 2 ms 2476 KB Ok
36 Correct 2 ms 2652 KB Ok
37 Correct 2 ms 2652 KB Ok
38 Correct 1 ms 2652 KB Ok
39 Correct 1 ms 2396 KB Ok
40 Correct 2 ms 2392 KB Ok
41 Correct 3 ms 2652 KB Ok
42 Correct 2 ms 2648 KB Ok
43 Correct 1 ms 2652 KB Ok
44 Correct 3 ms 2908 KB Ok
45 Correct 3 ms 2908 KB Ok
46 Correct 7 ms 2904 KB Ok
47 Correct 3 ms 2904 KB Ok
48 Correct 5 ms 2908 KB Ok
49 Correct 3 ms 2908 KB Ok
50 Correct 4 ms 2908 KB Ok
51 Correct 3 ms 2908 KB Ok
52 Correct 3 ms 3164 KB Ok
53 Correct 5 ms 2956 KB Ok
54 Correct 67 ms 10084 KB Ok
55 Correct 67 ms 10064 KB Ok
56 Correct 62 ms 10324 KB Ok
57 Correct 54 ms 8712 KB Ok
58 Correct 70 ms 9552 KB Ok
59 Correct 54 ms 9044 KB Ok
60 Correct 53 ms 8532 KB Ok
61 Correct 43 ms 9300 KB Ok
62 Correct 70 ms 9968 KB Ok
63 Correct 49 ms 8792 KB Ok
64 Correct 63 ms 10068 KB Ok
65 Correct 61 ms 9804 KB Ok
66 Correct 55 ms 9376 KB Ok
67 Correct 55 ms 9372 KB Ok
68 Correct 52 ms 9680 KB Ok
69 Correct 128 ms 19080 KB Ok
70 Correct 124 ms 18768 KB Ok
71 Correct 143 ms 17744 KB Ok
72 Correct 119 ms 19028 KB Ok
73 Correct 122 ms 18208 KB Ok
74 Correct 121 ms 18000 KB Ok
75 Correct 127 ms 18580 KB Ok
76 Correct 124 ms 19284 KB Ok
77 Correct 131 ms 17480 KB Ok
78 Correct 131 ms 19088 KB Ok
79 Correct 137 ms 18260 KB Ok
80 Correct 128 ms 18780 KB Ok
81 Correct 121 ms 18952 KB Ok
82 Correct 128 ms 18256 KB Ok
83 Correct 128 ms 18564 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 344 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 0 ms 344 KB Ok
14 Correct 0 ms 604 KB Ok
15 Correct 1 ms 348 KB Ok
16 Correct 0 ms 600 KB Ok
17 Correct 0 ms 348 KB Ok
18 Correct 2 ms 604 KB Ok
19 Correct 8 ms 1628 KB Ok
20 Correct 4 ms 860 KB Ok
21 Correct 9 ms 1704 KB Ok
22 Correct 5 ms 1116 KB Ok
23 Correct 0 ms 600 KB Ok
24 Correct 0 ms 348 KB Ok
25 Correct 0 ms 348 KB Ok
26 Correct 0 ms 348 KB Ok
27 Correct 0 ms 348 KB Ok
28 Correct 0 ms 428 KB Ok
29 Correct 1 ms 348 KB Ok
30 Correct 0 ms 348 KB Ok
31 Correct 1 ms 348 KB Ok
32 Correct 0 ms 348 KB Ok
33 Correct 0 ms 348 KB Ok
34 Correct 0 ms 344 KB Ok
35 Correct 0 ms 348 KB Ok
36 Correct 0 ms 348 KB Ok
37 Correct 0 ms 344 KB Ok
38 Correct 0 ms 348 KB Ok
39 Correct 75 ms 17744 KB Ok
40 Correct 66 ms 17484 KB Ok
41 Correct 119 ms 22672 KB Ok
42 Correct 97 ms 20748 KB Ok
43 Correct 54 ms 11488 KB Ok
44 Correct 89 ms 22100 KB Ok
45 Correct 2 ms 2652 KB Ok
46 Correct 2 ms 2476 KB Ok
47 Correct 2 ms 2652 KB Ok
48 Correct 2 ms 2652 KB Ok
49 Correct 1 ms 2652 KB Ok
50 Correct 1 ms 2396 KB Ok
51 Correct 2 ms 2392 KB Ok
52 Correct 3 ms 2652 KB Ok
53 Correct 2 ms 2648 KB Ok
54 Correct 1 ms 2652 KB Ok
55 Correct 3 ms 2908 KB Ok
56 Correct 3 ms 2908 KB Ok
57 Correct 7 ms 2904 KB Ok
58 Correct 3 ms 2904 KB Ok
59 Correct 5 ms 2908 KB Ok
60 Correct 3 ms 2908 KB Ok
61 Correct 4 ms 2908 KB Ok
62 Correct 3 ms 2908 KB Ok
63 Correct 3 ms 3164 KB Ok
64 Correct 5 ms 2956 KB Ok
65 Correct 67 ms 10084 KB Ok
66 Correct 67 ms 10064 KB Ok
67 Correct 62 ms 10324 KB Ok
68 Correct 54 ms 8712 KB Ok
69 Correct 70 ms 9552 KB Ok
70 Correct 54 ms 9044 KB Ok
71 Correct 53 ms 8532 KB Ok
72 Correct 43 ms 9300 KB Ok
73 Correct 70 ms 9968 KB Ok
74 Correct 49 ms 8792 KB Ok
75 Correct 63 ms 10068 KB Ok
76 Correct 61 ms 9804 KB Ok
77 Correct 55 ms 9376 KB Ok
78 Correct 55 ms 9372 KB Ok
79 Correct 52 ms 9680 KB Ok
80 Correct 128 ms 19080 KB Ok
81 Correct 124 ms 18768 KB Ok
82 Correct 143 ms 17744 KB Ok
83 Correct 119 ms 19028 KB Ok
84 Correct 122 ms 18208 KB Ok
85 Correct 121 ms 18000 KB Ok
86 Correct 127 ms 18580 KB Ok
87 Correct 124 ms 19284 KB Ok
88 Correct 131 ms 17480 KB Ok
89 Correct 131 ms 19088 KB Ok
90 Correct 137 ms 18260 KB Ok
91 Correct 128 ms 18780 KB Ok
92 Correct 121 ms 18952 KB Ok
93 Correct 128 ms 18256 KB Ok
94 Correct 128 ms 18564 KB Ok
95 Runtime error 74 ms 28496 KB Execution killed with signal 11
96 Halted 0 ms 0 KB -