oj.uz

Submission #1116251

# Submission time Handle Problem Language Result Execution time Memory
1116251 2024-11-21T11:38:39 Z KK_1729 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 33352 KB 
#include <bits/stdc++.h>
using namespace std;

// #define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

vector<int> possible(int x, int n, int m){
    vector<vector<int>> graph(x+1); // edge from i to j iff pref[i] < pref[j]
    vector<int> indeg(x+1);
    for (int i = m; i <= x; ++i){
        graph[i-m].pb(i);
        indeg[i] = 1;
    }

    for (int i = n; i <= x; ++i){
        graph[i].pb(i-n);
        indeg[i-n] = 1;
    }

    int val = 1;
    vector<int> visited(x+1);
    vector<int> prefix(x+1);
    stack<int> s;
    FOR(i,0,x+1){
        if (indeg[i] == 0){
            s.push(i);
        }
    }
    if (s.empty()){
        return {};
    }
        while (!s.empty()){
            int current = s.top();
            s.pop();
            if (visited[current]){
                return {};
            }
            prefix[current] = val;
            val++;
            for (auto item: graph[current]){
                s.push(item);
            }
            visited[current] = 1;
        }

    FOR(i,0,x+1){
        if (!visited[i]) return {};
    }
    
    return prefix;
}
void solve(){
    int n, m; cin >> n >> m;

    int l = 0; int r = 500000;
    vector<int> best;
    while (l < r){
        int mid = (l+r)/2;
        if (l+1 == r){
            if (!possible(r, n, m).empty()){
                best = possible(r, n, m);
            }else{
                best = possible(l, n, m);
            }
            break;
        }
        vector<int> o = possible(mid, n, m);
        // cout << l << r << mid << endl;
        if (!o.empty()){
            // cout << mid << endl;
            l = mid;
            best = o;
        }else{
            r = mid;
        }
    }
    // printVector(possible(7, 3, 6));
    // printVector(best);
    cout << best.size()-1 << endl;
    FOR(i,1,best.size()) cout << best[i]-best[i-1] << " ";
    cout << endl;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; cin >> t;
    while (t--) solve();
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
sequence.cpp:88:5: note: in expansion of macro 'FOR'
   88 |     FOR(i,1,best.size()) cout << best[i]-best[i-1] << " ";
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 17088 KB Ok
2 Correct 280 ms 17084 KB Ok
3 Correct 301 ms 17120 KB Ok
4 Correct 285 ms 17148 KB Ok
5 Correct 274 ms 16976 KB Ok
6 Correct 295 ms 17120 KB Ok
7 Correct 274 ms 16976 KB Ok
8 Correct 281 ms 16968 KB Ok
9 Correct 272 ms 17096 KB Ok
10 Correct 282 ms 16976 KB Ok
11 Correct 326 ms 16976 KB Ok
12 Correct 299 ms 16976 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 16988 KB Ok
2 Correct 287 ms 17064 KB Ok
3 Correct 291 ms 17144 KB Ok
4 Correct 300 ms 17144 KB Ok
5 Correct 271 ms 16976 KB Ok
6 Correct 297 ms 17120 KB Ok
7 Correct 335 ms 17376 KB Ok
8 Correct 323 ms 17132 KB Ok
9 Correct 369 ms 17628 KB Ok
10 Correct 314 ms 17376 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 16976 KB Ok
2 Correct 282 ms 17012 KB Ok
3 Correct 271 ms 17116 KB Ok
4 Correct 311 ms 16976 KB Ok
5 Correct 284 ms 16976 KB Ok
6 Correct 295 ms 16976 KB Ok
7 Correct 305 ms 17024 KB Ok
8 Correct 290 ms 17088 KB Ok
9 Correct 280 ms 16976 KB Ok
10 Correct 292 ms 16980 KB Ok
11 Correct 278 ms 16976 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 16976 KB Ok
2 Correct 290 ms 16976 KB Ok
3 Correct 274 ms 17036 KB Ok
4 Correct 287 ms 16976 KB Ok
5 Correct 273 ms 16976 KB Ok
6 Correct 804 ms 22112 KB Ok
7 Correct 746 ms 19996 KB Ok
8 Correct 1239 ms 23268 KB Ok
9 Correct 970 ms 23076 KB Ok
10 Correct 714 ms 19680 KB Ok
11 Correct 1042 ms 23688 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 17088 KB Ok
2 Correct 280 ms 17084 KB Ok
3 Correct 301 ms 17120 KB Ok
4 Correct 285 ms 17148 KB Ok
5 Correct 274 ms 16976 KB Ok
6 Correct 295 ms 17120 KB Ok
7 Correct 274 ms 16976 KB Ok
8 Correct 281 ms 16968 KB Ok
9 Correct 272 ms 17096 KB Ok
10 Correct 282 ms 16976 KB Ok
11 Correct 326 ms 16976 KB Ok
12 Correct 299 ms 16976 KB Ok
13 Correct 99 ms 16976 KB Ok
14 Correct 282 ms 17012 KB Ok
15 Correct 271 ms 17116 KB Ok
16 Correct 311 ms 16976 KB Ok
17 Correct 284 ms 16976 KB Ok
18 Correct 295 ms 16976 KB Ok
19 Correct 305 ms 17024 KB Ok
20 Correct 290 ms 17088 KB Ok
21 Correct 280 ms 16976 KB Ok
22 Correct 292 ms 16980 KB Ok
23 Correct 278 ms 16976 KB Ok
24 Correct 303 ms 17120 KB Ok
25 Correct 310 ms 17144 KB Ok
26 Correct 293 ms 17112 KB Ok
27 Correct 277 ms 16976 KB Ok
28 Correct 286 ms 16984 KB Ok
29 Correct 313 ms 17120 KB Ok
30 Correct 279 ms 17088 KB Ok
31 Correct 280 ms 17112 KB Ok
32 Correct 298 ms 17128 KB Ok
33 Correct 276 ms 16952 KB Ok
34 Correct 293 ms 17120 KB Ok
35 Correct 281 ms 17144 KB Ok
36 Correct 295 ms 17232 KB Ok
37 Correct 308 ms 17120 KB Ok
38 Correct 303 ms 17120 KB Ok
39 Correct 313 ms 17220 KB Ok
40 Correct 289 ms 17204 KB Ok
41 Correct 298 ms 17120 KB Ok
42 Correct 298 ms 17148 KB Ok
43 Correct 286 ms 17116 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 17088 KB Ok
2 Correct 280 ms 17084 KB Ok
3 Correct 301 ms 17120 KB Ok
4 Correct 285 ms 17148 KB Ok
5 Correct 274 ms 16976 KB Ok
6 Correct 295 ms 17120 KB Ok
7 Correct 274 ms 16976 KB Ok
8 Correct 281 ms 16968 KB Ok
9 Correct 272 ms 17096 KB Ok
10 Correct 282 ms 16976 KB Ok
11 Correct 326 ms 16976 KB Ok
12 Correct 299 ms 16976 KB Ok
13 Correct 303 ms 16988 KB Ok
14 Correct 287 ms 17064 KB Ok
15 Correct 291 ms 17144 KB Ok
16 Correct 300 ms 17144 KB Ok
17 Correct 271 ms 16976 KB Ok
18 Correct 297 ms 17120 KB Ok
19 Correct 335 ms 17376 KB Ok
20 Correct 323 ms 17132 KB Ok
21 Correct 369 ms 17628 KB Ok
22 Correct 314 ms 17376 KB Ok
23 Correct 99 ms 16976 KB Ok
24 Correct 282 ms 17012 KB Ok
25 Correct 271 ms 17116 KB Ok
26 Correct 311 ms 16976 KB Ok
27 Correct 284 ms 16976 KB Ok
28 Correct 295 ms 16976 KB Ok
29 Correct 305 ms 17024 KB Ok
30 Correct 290 ms 17088 KB Ok
31 Correct 280 ms 16976 KB Ok
32 Correct 292 ms 16980 KB Ok
33 Correct 278 ms 16976 KB Ok
34 Correct 303 ms 17120 KB Ok
35 Correct 310 ms 17144 KB Ok
36 Correct 293 ms 17112 KB Ok
37 Correct 277 ms 16976 KB Ok
38 Correct 286 ms 16984 KB Ok
39 Correct 313 ms 17120 KB Ok
40 Correct 279 ms 17088 KB Ok
41 Correct 280 ms 17112 KB Ok
42 Correct 298 ms 17128 KB Ok
43 Correct 276 ms 16952 KB Ok
44 Correct 293 ms 17120 KB Ok
45 Correct 281 ms 17144 KB Ok
46 Correct 295 ms 17232 KB Ok
47 Correct 308 ms 17120 KB Ok
48 Correct 303 ms 17120 KB Ok
49 Correct 313 ms 17220 KB Ok
50 Correct 289 ms 17204 KB Ok
51 Correct 298 ms 17120 KB Ok
52 Correct 298 ms 17148 KB Ok
53 Correct 286 ms 17116 KB Ok
54 Correct 691 ms 19504 KB Ok
55 Correct 929 ms 19900 KB Ok
56 Correct 777 ms 19932 KB Ok
57 Correct 568 ms 19168 KB Ok
58 Correct 742 ms 19424 KB Ok
59 Correct 737 ms 19364 KB Ok
60 Correct 560 ms 19168 KB Ok
61 Correct 627 ms 19076 KB Ok
62 Correct 866 ms 19956 KB Ok
63 Correct 651 ms 19420 KB Ok
64 Correct 829 ms 19936 KB Ok
65 Correct 801 ms 19676 KB Ok
66 Correct 729 ms 19404 KB Ok
67 Correct 585 ms 19164 KB Ok
68 Correct 710 ms 19424 KB Ok
69 Correct 1346 ms 23364 KB Ok
70 Correct 1229 ms 23592 KB Ok
71 Correct 1251 ms 23644 KB Ok
72 Correct 1180 ms 23004 KB Ok
73 Correct 1310 ms 23516 KB Ok
74 Correct 1358 ms 23596 KB Ok
75 Correct 1419 ms 23384 KB Ok
76 Correct 1200 ms 23140 KB Ok
77 Correct 1371 ms 23584 KB Ok
78 Correct 1214 ms 23100 KB Ok
79 Correct 1161 ms 23520 KB Ok
80 Correct 1204 ms 23588 KB Ok
81 Correct 1173 ms 23320 KB Ok
82 Correct 1215 ms 23560 KB Ok
83 Correct 1197 ms 23520 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 17088 KB Ok
2 Correct 280 ms 17084 KB Ok
3 Correct 301 ms 17120 KB Ok
4 Correct 285 ms 17148 KB Ok
5 Correct 274 ms 16976 KB Ok
6 Correct 295 ms 17120 KB Ok
7 Correct 274 ms 16976 KB Ok
8 Correct 281 ms 16968 KB Ok
9 Correct 272 ms 17096 KB Ok
10 Correct 282 ms 16976 KB Ok
11 Correct 326 ms 16976 KB Ok
12 Correct 299 ms 16976 KB Ok
13 Correct 303 ms 16988 KB Ok
14 Correct 287 ms 17064 KB Ok
15 Correct 291 ms 17144 KB Ok
16 Correct 300 ms 17144 KB Ok
17 Correct 271 ms 16976 KB Ok
18 Correct 297 ms 17120 KB Ok
19 Correct 335 ms 17376 KB Ok
20 Correct 323 ms 17132 KB Ok
21 Correct 369 ms 17628 KB Ok
22 Correct 314 ms 17376 KB Ok
23 Correct 99 ms 16976 KB Ok
24 Correct 282 ms 17012 KB Ok
25 Correct 271 ms 17116 KB Ok
26 Correct 311 ms 16976 KB Ok
27 Correct 284 ms 16976 KB Ok
28 Correct 295 ms 16976 KB Ok
29 Correct 305 ms 17024 KB Ok
30 Correct 290 ms 17088 KB Ok
31 Correct 280 ms 16976 KB Ok
32 Correct 292 ms 16980 KB Ok
33 Correct 278 ms 16976 KB Ok
34 Correct 298 ms 16976 KB Ok
35 Correct 290 ms 16976 KB Ok
36 Correct 274 ms 17036 KB Ok
37 Correct 287 ms 16976 KB Ok
38 Correct 273 ms 16976 KB Ok
39 Correct 804 ms 22112 KB Ok
40 Correct 746 ms 19996 KB Ok
41 Correct 1239 ms 23268 KB Ok
42 Correct 970 ms 23076 KB Ok
43 Correct 714 ms 19680 KB Ok
44 Correct 1042 ms 23688 KB Ok
45 Correct 303 ms 17120 KB Ok
46 Correct 310 ms 17144 KB Ok
47 Correct 293 ms 17112 KB Ok
48 Correct 277 ms 16976 KB Ok
49 Correct 286 ms 16984 KB Ok
50 Correct 313 ms 17120 KB Ok
51 Correct 279 ms 17088 KB Ok
52 Correct 280 ms 17112 KB Ok
53 Correct 298 ms 17128 KB Ok
54 Correct 276 ms 16952 KB Ok
55 Correct 293 ms 17120 KB Ok
56 Correct 281 ms 17144 KB Ok
57 Correct 295 ms 17232 KB Ok
58 Correct 308 ms 17120 KB Ok
59 Correct 303 ms 17120 KB Ok
60 Correct 313 ms 17220 KB Ok
61 Correct 289 ms 17204 KB Ok
62 Correct 298 ms 17120 KB Ok
63 Correct 298 ms 17148 KB Ok
64 Correct 286 ms 17116 KB Ok
65 Correct 691 ms 19504 KB Ok
66 Correct 929 ms 19900 KB Ok
67 Correct 777 ms 19932 KB Ok
68 Correct 568 ms 19168 KB Ok
69 Correct 742 ms 19424 KB Ok
70 Correct 737 ms 19364 KB Ok
71 Correct 560 ms 19168 KB Ok
72 Correct 627 ms 19076 KB Ok
73 Correct 866 ms 19956 KB Ok
74 Correct 651 ms 19420 KB Ok
75 Correct 829 ms 19936 KB Ok
76 Correct 801 ms 19676 KB Ok
77 Correct 729 ms 19404 KB Ok
78 Correct 585 ms 19164 KB Ok
79 Correct 710 ms 19424 KB Ok
80 Correct 1346 ms 23364 KB Ok
81 Correct 1229 ms 23592 KB Ok
82 Correct 1251 ms 23644 KB Ok
83 Correct 1180 ms 23004 KB Ok
84 Correct 1310 ms 23516 KB Ok
85 Correct 1358 ms 23596 KB Ok
86 Correct 1419 ms 23384 KB Ok
87 Correct 1200 ms 23140 KB Ok
88 Correct 1371 ms 23584 KB Ok
89 Correct 1214 ms 23100 KB Ok
90 Correct 1161 ms 23520 KB Ok
91 Correct 1204 ms 23588 KB Ok
92 Correct 1173 ms 23320 KB Ok
93 Correct 1215 ms 23560 KB Ok
94 Correct 1197 ms 23520 KB Ok
95 Correct 1304 ms 24000 KB Ok
96 Execution timed out 2073 ms 33352 KB Time limit exceeded
97 Halted 0 ms 0 KB -