oj.uz

Submission #389773

# Submission time Handle Problem Language Result Execution time Memory
389773 2021-04-14T14:03:38 Z BartolM Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 39428 KB 
#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=4e5+5;

int n, m;
vector <int> ls[N]; //(i->j) i veci od j
int in[N], bio[N], sol[N];
queue <int> Q;

void reset(int x) {
    for (int i=0; i<=x; ++i) ls[i].clear(), in[i]=0, bio[i]=0;
}

void build(int x) {
    for (int i=1; i<=x; ++i) {
        if (i-n>=0) ls[i-n].pb(i), in[i]++;
        if (i-m>=0) ls[i].pb(i-m), in[i-m]++;
    }
}

int dfs(int node) {
    if (bio[node]==2) return 0;
    if (bio[node]==1) return 1;
    bio[node]=1;
    int ret=0;
    for (int sus:ls[node]) ret|=dfs(sus);
    bio[node]=2;
    return ret;
}

void topo_sort(int gr) {
    for (int i=0; i<=gr; ++i) if (!in[i]) Q.push(i);
    int curr=gr+1;
    while (!Q.empty()) {
        int node=Q.front();
        Q.pop();
        sol[node]=curr--;
        for (int sus:ls[node]) {
            in[sus]--;
            if (!in[sus]) Q.push(sus);
        }
    }
}

void solve() {
    int lo=0, hi=2*max(n, m), mid;
    while (lo<hi) {
        mid=(lo+hi+1)/2;
        build(mid);
        int fl=0;
        for (int i=0; i<=mid && !fl; ++i) fl+=dfs(i);
        if (fl) hi=mid-1;
        else lo=mid;
        reset(mid);
    }
    build(lo);
    topo_sort(lo);
    printf("%d\n", lo);
    for (int i=1; i<=lo; ++i) printf("%d ", sol[i]-sol[i-1]);
    printf("\n");
    reset(lo);
}

void load() {
    scanf("%d %d", &n, &m);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        load();
        solve();
    }
    return 0;
}

Compilation message

sequence.cpp: In function 'void load()':
sequence.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 6 ms 9692 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 6 ms 9676 KB Ok
6 Correct 7 ms 9680 KB Ok
7 Correct 6 ms 9676 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 6 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 6 ms 9612 KB Ok
12 Correct 6 ms 9676 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9696 KB Ok
2 Correct 6 ms 9680 KB Ok
3 Correct 6 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 6 ms 9676 KB Ok
6 Correct 13 ms 9932 KB Ok
7 Correct 42 ms 11076 KB Ok
8 Correct 21 ms 10268 KB Ok
9 Correct 46 ms 11208 KB Ok
10 Correct 32 ms 10564 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 5 ms 9676 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 6 ms 9692 KB Ok
6 Correct 7 ms 9676 KB Ok
7 Correct 7 ms 9804 KB Ok
8 Correct 6 ms 9692 KB Ok
9 Correct 6 ms 9700 KB Ok
10 Correct 6 ms 9696 KB Ok
11 Correct 6 ms 9676 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 6 ms 9676 KB Ok
4 Correct 6 ms 9692 KB Ok
5 Correct 6 ms 9676 KB Ok
6 Correct 399 ms 26816 KB Ok
7 Correct 375 ms 29508 KB Ok
8 Correct 776 ms 31044 KB Ok
9 Correct 504 ms 29508 KB Ok
10 Correct 257 ms 20820 KB Ok
11 Correct 438 ms 31128 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 6 ms 9692 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 6 ms 9676 KB Ok
6 Correct 7 ms 9680 KB Ok
7 Correct 6 ms 9676 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 6 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 6 ms 9612 KB Ok
12 Correct 6 ms 9676 KB Ok
13 Correct 6 ms 9676 KB Ok
14 Correct 6 ms 9676 KB Ok
15 Correct 5 ms 9676 KB Ok
16 Correct 6 ms 9676 KB Ok
17 Correct 6 ms 9692 KB Ok
18 Correct 7 ms 9676 KB Ok
19 Correct 7 ms 9804 KB Ok
20 Correct 6 ms 9692 KB Ok
21 Correct 6 ms 9700 KB Ok
22 Correct 6 ms 9696 KB Ok
23 Correct 6 ms 9676 KB Ok
24 Correct 11 ms 9804 KB Ok
25 Correct 10 ms 9864 KB Ok
26 Correct 11 ms 9908 KB Ok
27 Correct 11 ms 9828 KB Ok
28 Correct 10 ms 9884 KB Ok
29 Correct 12 ms 9804 KB Ok
30 Correct 10 ms 9804 KB Ok
31 Correct 11 ms 9804 KB Ok
32 Correct 11 ms 9824 KB Ok
33 Correct 11 ms 9804 KB Ok
34 Correct 19 ms 10128 KB Ok
35 Correct 20 ms 10196 KB Ok
36 Correct 19 ms 10080 KB Ok
37 Correct 20 ms 10188 KB Ok
38 Correct 19 ms 10188 KB Ok
39 Correct 19 ms 10080 KB Ok
40 Correct 21 ms 10104 KB Ok
41 Correct 21 ms 10160 KB Ok
42 Correct 20 ms 10192 KB Ok
43 Correct 21 ms 10188 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 6 ms 9692 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 6 ms 9676 KB Ok
6 Correct 7 ms 9680 KB Ok
7 Correct 6 ms 9676 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 6 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 6 ms 9612 KB Ok
12 Correct 6 ms 9676 KB Ok
13 Correct 6 ms 9696 KB Ok
14 Correct 6 ms 9680 KB Ok
15 Correct 6 ms 9676 KB Ok
16 Correct 6 ms 9676 KB Ok
17 Correct 6 ms 9676 KB Ok
18 Correct 13 ms 9932 KB Ok
19 Correct 42 ms 11076 KB Ok
20 Correct 21 ms 10268 KB Ok
21 Correct 46 ms 11208 KB Ok
22 Correct 32 ms 10564 KB Ok
23 Correct 6 ms 9676 KB Ok
24 Correct 6 ms 9676 KB Ok
25 Correct 5 ms 9676 KB Ok
26 Correct 6 ms 9676 KB Ok
27 Correct 6 ms 9692 KB Ok
28 Correct 7 ms 9676 KB Ok
29 Correct 7 ms 9804 KB Ok
30 Correct 6 ms 9692 KB Ok
31 Correct 6 ms 9700 KB Ok
32 Correct 6 ms 9696 KB Ok
33 Correct 6 ms 9676 KB Ok
34 Correct 11 ms 9804 KB Ok
35 Correct 10 ms 9864 KB Ok
36 Correct 11 ms 9908 KB Ok
37 Correct 11 ms 9828 KB Ok
38 Correct 10 ms 9884 KB Ok
39 Correct 12 ms 9804 KB Ok
40 Correct 10 ms 9804 KB Ok
41 Correct 11 ms 9804 KB Ok
42 Correct 11 ms 9824 KB Ok
43 Correct 11 ms 9804 KB Ok
44 Correct 19 ms 10128 KB Ok
45 Correct 20 ms 10196 KB Ok
46 Correct 19 ms 10080 KB Ok
47 Correct 20 ms 10188 KB Ok
48 Correct 19 ms 10188 KB Ok
49 Correct 19 ms 10080 KB Ok
50 Correct 21 ms 10104 KB Ok
51 Correct 21 ms 10160 KB Ok
52 Correct 20 ms 10192 KB Ok
53 Correct 21 ms 10188 KB Ok
54 Correct 246 ms 15896 KB Ok
55 Correct 316 ms 16224 KB Ok
56 Correct 311 ms 16164 KB Ok
57 Correct 206 ms 15332 KB Ok
58 Correct 242 ms 15864 KB Ok
59 Correct 228 ms 15776 KB Ok
60 Correct 196 ms 15260 KB Ok
61 Correct 213 ms 15428 KB Ok
62 Correct 282 ms 16152 KB Ok
63 Correct 234 ms 15564 KB Ok
64 Correct 282 ms 15972 KB Ok
65 Correct 259 ms 16064 KB Ok
66 Correct 235 ms 15556 KB Ok
67 Correct 217 ms 15212 KB Ok
68 Correct 236 ms 15940 KB Ok
69 Correct 1008 ms 24156 KB Ok
70 Correct 1066 ms 25180 KB Ok
71 Correct 938 ms 23604 KB Ok
72 Correct 1207 ms 24340 KB Ok
73 Correct 1048 ms 24040 KB Ok
74 Correct 992 ms 23176 KB Ok
75 Correct 946 ms 23232 KB Ok
76 Correct 1094 ms 24940 KB Ok
77 Correct 843 ms 22944 KB Ok
78 Correct 993 ms 24680 KB Ok
79 Correct 920 ms 24332 KB Ok
80 Correct 1118 ms 24088 KB Ok
81 Correct 1295 ms 24472 KB Ok
82 Correct 1191 ms 24172 KB Ok
83 Correct 873 ms 23316 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Ok
2 Correct 6 ms 9676 KB Ok
3 Correct 6 ms 9692 KB Ok
4 Correct 6 ms 9676 KB Ok
5 Correct 6 ms 9676 KB Ok
6 Correct 7 ms 9680 KB Ok
7 Correct 6 ms 9676 KB Ok
8 Correct 6 ms 9676 KB Ok
9 Correct 6 ms 9676 KB Ok
10 Correct 6 ms 9676 KB Ok
11 Correct 6 ms 9612 KB Ok
12 Correct 6 ms 9676 KB Ok
13 Correct 6 ms 9696 KB Ok
14 Correct 6 ms 9680 KB Ok
15 Correct 6 ms 9676 KB Ok
16 Correct 6 ms 9676 KB Ok
17 Correct 6 ms 9676 KB Ok
18 Correct 13 ms 9932 KB Ok
19 Correct 42 ms 11076 KB Ok
20 Correct 21 ms 10268 KB Ok
21 Correct 46 ms 11208 KB Ok
22 Correct 32 ms 10564 KB Ok
23 Correct 6 ms 9676 KB Ok
24 Correct 6 ms 9676 KB Ok
25 Correct 5 ms 9676 KB Ok
26 Correct 6 ms 9676 KB Ok
27 Correct 6 ms 9692 KB Ok
28 Correct 7 ms 9676 KB Ok
29 Correct 7 ms 9804 KB Ok
30 Correct 6 ms 9692 KB Ok
31 Correct 6 ms 9700 KB Ok
32 Correct 6 ms 9696 KB Ok
33 Correct 6 ms 9676 KB Ok
34 Correct 6 ms 9676 KB Ok
35 Correct 6 ms 9676 KB Ok
36 Correct 6 ms 9676 KB Ok
37 Correct 6 ms 9692 KB Ok
38 Correct 6 ms 9676 KB Ok
39 Correct 399 ms 26816 KB Ok
40 Correct 375 ms 29508 KB Ok
41 Correct 776 ms 31044 KB Ok
42 Correct 504 ms 29508 KB Ok
43 Correct 257 ms 20820 KB Ok
44 Correct 438 ms 31128 KB Ok
45 Correct 11 ms 9804 KB Ok
46 Correct 10 ms 9864 KB Ok
47 Correct 11 ms 9908 KB Ok
48 Correct 11 ms 9828 KB Ok
49 Correct 10 ms 9884 KB Ok
50 Correct 12 ms 9804 KB Ok
51 Correct 10 ms 9804 KB Ok
52 Correct 11 ms 9804 KB Ok
53 Correct 11 ms 9824 KB Ok
54 Correct 11 ms 9804 KB Ok
55 Correct 19 ms 10128 KB Ok
56 Correct 20 ms 10196 KB Ok
57 Correct 19 ms 10080 KB Ok
58 Correct 20 ms 10188 KB Ok
59 Correct 19 ms 10188 KB Ok
60 Correct 19 ms 10080 KB Ok
61 Correct 21 ms 10104 KB Ok
62 Correct 21 ms 10160 KB Ok
63 Correct 20 ms 10192 KB Ok
64 Correct 21 ms 10188 KB Ok
65 Correct 246 ms 15896 KB Ok
66 Correct 316 ms 16224 KB Ok
67 Correct 311 ms 16164 KB Ok
68 Correct 206 ms 15332 KB Ok
69 Correct 242 ms 15864 KB Ok
70 Correct 228 ms 15776 KB Ok
71 Correct 196 ms 15260 KB Ok
72 Correct 213 ms 15428 KB Ok
73 Correct 282 ms 16152 KB Ok
74 Correct 234 ms 15564 KB Ok
75 Correct 282 ms 15972 KB Ok
76 Correct 259 ms 16064 KB Ok
77 Correct 235 ms 15556 KB Ok
78 Correct 217 ms 15212 KB Ok
79 Correct 236 ms 15940 KB Ok
80 Correct 1008 ms 24156 KB Ok
81 Correct 1066 ms 25180 KB Ok
82 Correct 938 ms 23604 KB Ok
83 Correct 1207 ms 24340 KB Ok
84 Correct 1048 ms 24040 KB Ok
85 Correct 992 ms 23176 KB Ok
86 Correct 946 ms 23232 KB Ok
87 Correct 1094 ms 24940 KB Ok
88 Correct 843 ms 22944 KB Ok
89 Correct 993 ms 24680 KB Ok
90 Correct 920 ms 24332 KB Ok
91 Correct 1118 ms 24088 KB Ok
92 Correct 1295 ms 24472 KB Ok
93 Correct 1191 ms 24172 KB Ok
94 Correct 873 ms 23316 KB Ok
95 Correct 766 ms 26180 KB Ok
96 Correct 1179 ms 33600 KB Ok
97 Correct 1002 ms 30088 KB Ok
98 Correct 653 ms 30376 KB Ok
99 Correct 914 ms 28800 KB Ok
100 Correct 913 ms 29228 KB Ok
101 Correct 935 ms 31464 KB Ok
102 Correct 906 ms 29508 KB Ok
103 Correct 884 ms 31368 KB Ok
104 Correct 1085 ms 33220 KB Ok
105 Correct 1016 ms 32552 KB Ok
106 Correct 869 ms 32060 KB Ok
107 Correct 922 ms 31608 KB Ok
108 Correct 1160 ms 32872 KB Ok
109 Correct 1121 ms 33760 KB Ok
110 Execution timed out 2090 ms 39428 KB Time limit exceeded
111 Halted 0 ms 0 KB -