oj.uz

Submission #1116246

# Submission time Handle Problem Language Result Execution time Memory
1116246 2024-11-21T11:35:42 Z KK_1729 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 50084 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);
    FOR(i,0,x+1){
        // cout << i << ": ";
        // printVector(graph[i]);
    }
    stack<int> s;
    FOR(i,0,x+1){
        if (indeg[i] == 0){
            s.push(i);
            // cout << i << endl;
        }
    }
    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 = 1000000;
    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: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
sequence.cpp:93:5: note: in expansion of macro 'FOR'
   93 |     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 729 ms 39584 KB Ok
2 Correct 818 ms 39596 KB Ok
3 Correct 721 ms 39608 KB Ok
4 Correct 788 ms 39568 KB Ok
5 Correct 710 ms 39760 KB Ok
6 Correct 711 ms 39620 KB Ok
7 Correct 741 ms 39624 KB Ok
8 Correct 692 ms 39768 KB Ok
9 Correct 690 ms 39612 KB Ok
10 Correct 685 ms 39592 KB Ok
11 Correct 688 ms 39608 KB Ok
12 Correct 746 ms 39588 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 39624 KB Ok
2 Correct 714 ms 39588 KB Ok
3 Correct 733 ms 39588 KB Ok
4 Correct 730 ms 39600 KB Ok
5 Correct 749 ms 39580 KB Ok
6 Correct 729 ms 39584 KB Ok
7 Correct 775 ms 39904 KB Ok
8 Correct 778 ms 39692 KB Ok
9 Correct 747 ms 40012 KB Ok
10 Correct 733 ms 39792 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 39588 KB Ok
2 Correct 720 ms 39600 KB Ok
3 Correct 724 ms 39888 KB Ok
4 Correct 739 ms 39588 KB Ok
5 Correct 751 ms 39592 KB Ok
6 Correct 756 ms 39548 KB Ok
7 Correct 776 ms 39620 KB Ok
8 Correct 747 ms 39584 KB Ok
9 Correct 737 ms 39600 KB Ok
10 Correct 795 ms 39572 KB Ok
11 Correct 777 ms 39836 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 39588 KB Ok
2 Correct 743 ms 39560 KB Ok
3 Correct 744 ms 39684 KB Ok
4 Correct 770 ms 39588 KB Ok
5 Correct 714 ms 39580 KB Ok
6 Correct 1221 ms 43208 KB Ok
7 Correct 1185 ms 41452 KB Ok
8 Correct 1742 ms 45296 KB Ok
9 Correct 1461 ms 44592 KB Ok
10 Correct 1117 ms 41980 KB Ok
11 Correct 1414 ms 43000 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 39584 KB Ok
2 Correct 818 ms 39596 KB Ok
3 Correct 721 ms 39608 KB Ok
4 Correct 788 ms 39568 KB Ok
5 Correct 710 ms 39760 KB Ok
6 Correct 711 ms 39620 KB Ok
7 Correct 741 ms 39624 KB Ok
8 Correct 692 ms 39768 KB Ok
9 Correct 690 ms 39612 KB Ok
10 Correct 685 ms 39592 KB Ok
11 Correct 688 ms 39608 KB Ok
12 Correct 746 ms 39588 KB Ok
13 Correct 213 ms 39588 KB Ok
14 Correct 720 ms 39600 KB Ok
15 Correct 724 ms 39888 KB Ok
16 Correct 739 ms 39588 KB Ok
17 Correct 751 ms 39592 KB Ok
18 Correct 756 ms 39548 KB Ok
19 Correct 776 ms 39620 KB Ok
20 Correct 747 ms 39584 KB Ok
21 Correct 737 ms 39600 KB Ok
22 Correct 795 ms 39572 KB Ok
23 Correct 777 ms 39836 KB Ok
24 Correct 760 ms 39604 KB Ok
25 Correct 748 ms 39600 KB Ok
26 Correct 749 ms 39624 KB Ok
27 Correct 730 ms 39592 KB Ok
28 Correct 749 ms 39616 KB Ok
29 Correct 733 ms 39580 KB Ok
30 Correct 712 ms 39660 KB Ok
31 Correct 708 ms 39568 KB Ok
32 Correct 701 ms 39620 KB Ok
33 Correct 698 ms 39624 KB Ok
34 Correct 754 ms 39708 KB Ok
35 Correct 743 ms 39648 KB Ok
36 Correct 740 ms 39940 KB Ok
37 Correct 751 ms 39652 KB Ok
38 Correct 776 ms 39684 KB Ok
39 Correct 712 ms 39680 KB Ok
40 Correct 719 ms 39684 KB Ok
41 Correct 722 ms 41612 KB Ok
42 Correct 786 ms 39716 KB Ok
43 Correct 733 ms 39712 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 39584 KB Ok
2 Correct 818 ms 39596 KB Ok
3 Correct 721 ms 39608 KB Ok
4 Correct 788 ms 39568 KB Ok
5 Correct 710 ms 39760 KB Ok
6 Correct 711 ms 39620 KB Ok
7 Correct 741 ms 39624 KB Ok
8 Correct 692 ms 39768 KB Ok
9 Correct 690 ms 39612 KB Ok
10 Correct 685 ms 39592 KB Ok
11 Correct 688 ms 39608 KB Ok
12 Correct 746 ms 39588 KB Ok
13 Correct 719 ms 39624 KB Ok
14 Correct 714 ms 39588 KB Ok
15 Correct 733 ms 39588 KB Ok
16 Correct 730 ms 39600 KB Ok
17 Correct 749 ms 39580 KB Ok
18 Correct 729 ms 39584 KB Ok
19 Correct 775 ms 39904 KB Ok
20 Correct 778 ms 39692 KB Ok
21 Correct 747 ms 40012 KB Ok
22 Correct 733 ms 39792 KB Ok
23 Correct 213 ms 39588 KB Ok
24 Correct 720 ms 39600 KB Ok
25 Correct 724 ms 39888 KB Ok
26 Correct 739 ms 39588 KB Ok
27 Correct 751 ms 39592 KB Ok
28 Correct 756 ms 39548 KB Ok
29 Correct 776 ms 39620 KB Ok
30 Correct 747 ms 39584 KB Ok
31 Correct 737 ms 39600 KB Ok
32 Correct 795 ms 39572 KB Ok
33 Correct 777 ms 39836 KB Ok
34 Correct 760 ms 39604 KB Ok
35 Correct 748 ms 39600 KB Ok
36 Correct 749 ms 39624 KB Ok
37 Correct 730 ms 39592 KB Ok
38 Correct 749 ms 39616 KB Ok
39 Correct 733 ms 39580 KB Ok
40 Correct 712 ms 39660 KB Ok
41 Correct 708 ms 39568 KB Ok
42 Correct 701 ms 39620 KB Ok
43 Correct 698 ms 39624 KB Ok
44 Correct 754 ms 39708 KB Ok
45 Correct 743 ms 39648 KB Ok
46 Correct 740 ms 39940 KB Ok
47 Correct 751 ms 39652 KB Ok
48 Correct 776 ms 39684 KB Ok
49 Correct 712 ms 39680 KB Ok
50 Correct 719 ms 39684 KB Ok
51 Correct 722 ms 41612 KB Ok
52 Correct 786 ms 39716 KB Ok
53 Correct 733 ms 39712 KB Ok
54 Correct 1042 ms 41648 KB Ok
55 Correct 1260 ms 42188 KB Ok
56 Correct 1145 ms 42428 KB Ok
57 Correct 963 ms 41324 KB Ok
58 Correct 1164 ms 41836 KB Ok
59 Correct 1083 ms 41772 KB Ok
60 Correct 971 ms 41304 KB Ok
61 Correct 980 ms 41252 KB Ok
62 Correct 1347 ms 42068 KB Ok
63 Correct 1109 ms 41764 KB Ok
64 Correct 1279 ms 42020 KB Ok
65 Correct 1245 ms 42016 KB Ok
66 Correct 1149 ms 41448 KB Ok
67 Correct 1048 ms 41436 KB Ok
68 Correct 1165 ms 41788 KB Ok
69 Correct 1738 ms 45164 KB Ok
70 Correct 1727 ms 45380 KB Ok
71 Correct 1813 ms 45336 KB Ok
72 Correct 1456 ms 44828 KB Ok
73 Correct 1673 ms 45344 KB Ok
74 Correct 1608 ms 45548 KB Ok
75 Correct 1629 ms 45124 KB Ok
76 Correct 1603 ms 45096 KB Ok
77 Correct 1697 ms 45340 KB Ok
78 Correct 1634 ms 45012 KB Ok
79 Correct 1548 ms 45380 KB Ok
80 Correct 1582 ms 45516 KB Ok
81 Correct 1501 ms 45280 KB Ok
82 Correct 1637 ms 45376 KB Ok
83 Correct 1697 ms 45204 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 39584 KB Ok
2 Correct 818 ms 39596 KB Ok
3 Correct 721 ms 39608 KB Ok
4 Correct 788 ms 39568 KB Ok
5 Correct 710 ms 39760 KB Ok
6 Correct 711 ms 39620 KB Ok
7 Correct 741 ms 39624 KB Ok
8 Correct 692 ms 39768 KB Ok
9 Correct 690 ms 39612 KB Ok
10 Correct 685 ms 39592 KB Ok
11 Correct 688 ms 39608 KB Ok
12 Correct 746 ms 39588 KB Ok
13 Correct 719 ms 39624 KB Ok
14 Correct 714 ms 39588 KB Ok
15 Correct 733 ms 39588 KB Ok
16 Correct 730 ms 39600 KB Ok
17 Correct 749 ms 39580 KB Ok
18 Correct 729 ms 39584 KB Ok
19 Correct 775 ms 39904 KB Ok
20 Correct 778 ms 39692 KB Ok
21 Correct 747 ms 40012 KB Ok
22 Correct 733 ms 39792 KB Ok
23 Correct 213 ms 39588 KB Ok
24 Correct 720 ms 39600 KB Ok
25 Correct 724 ms 39888 KB Ok
26 Correct 739 ms 39588 KB Ok
27 Correct 751 ms 39592 KB Ok
28 Correct 756 ms 39548 KB Ok
29 Correct 776 ms 39620 KB Ok
30 Correct 747 ms 39584 KB Ok
31 Correct 737 ms 39600 KB Ok
32 Correct 795 ms 39572 KB Ok
33 Correct 777 ms 39836 KB Ok
34 Correct 815 ms 39588 KB Ok
35 Correct 743 ms 39560 KB Ok
36 Correct 744 ms 39684 KB Ok
37 Correct 770 ms 39588 KB Ok
38 Correct 714 ms 39580 KB Ok
39 Correct 1221 ms 43208 KB Ok
40 Correct 1185 ms 41452 KB Ok
41 Correct 1742 ms 45296 KB Ok
42 Correct 1461 ms 44592 KB Ok
43 Correct 1117 ms 41980 KB Ok
44 Correct 1414 ms 43000 KB Ok
45 Correct 760 ms 39604 KB Ok
46 Correct 748 ms 39600 KB Ok
47 Correct 749 ms 39624 KB Ok
48 Correct 730 ms 39592 KB Ok
49 Correct 749 ms 39616 KB Ok
50 Correct 733 ms 39580 KB Ok
51 Correct 712 ms 39660 KB Ok
52 Correct 708 ms 39568 KB Ok
53 Correct 701 ms 39620 KB Ok
54 Correct 698 ms 39624 KB Ok
55 Correct 754 ms 39708 KB Ok
56 Correct 743 ms 39648 KB Ok
57 Correct 740 ms 39940 KB Ok
58 Correct 751 ms 39652 KB Ok
59 Correct 776 ms 39684 KB Ok
60 Correct 712 ms 39680 KB Ok
61 Correct 719 ms 39684 KB Ok
62 Correct 722 ms 41612 KB Ok
63 Correct 786 ms 39716 KB Ok
64 Correct 733 ms 39712 KB Ok
65 Correct 1042 ms 41648 KB Ok
66 Correct 1260 ms 42188 KB Ok
67 Correct 1145 ms 42428 KB Ok
68 Correct 963 ms 41324 KB Ok
69 Correct 1164 ms 41836 KB Ok
70 Correct 1083 ms 41772 KB Ok
71 Correct 971 ms 41304 KB Ok
72 Correct 980 ms 41252 KB Ok
73 Correct 1347 ms 42068 KB Ok
74 Correct 1109 ms 41764 KB Ok
75 Correct 1279 ms 42020 KB Ok
76 Correct 1245 ms 42016 KB Ok
77 Correct 1149 ms 41448 KB Ok
78 Correct 1048 ms 41436 KB Ok
79 Correct 1165 ms 41788 KB Ok
80 Correct 1738 ms 45164 KB Ok
81 Correct 1727 ms 45380 KB Ok
82 Correct 1813 ms 45336 KB Ok
83 Correct 1456 ms 44828 KB Ok
84 Correct 1673 ms 45344 KB Ok
85 Correct 1608 ms 45548 KB Ok
86 Correct 1629 ms 45124 KB Ok
87 Correct 1603 ms 45096 KB Ok
88 Correct 1697 ms 45340 KB Ok
89 Correct 1634 ms 45012 KB Ok
90 Correct 1548 ms 45380 KB Ok
91 Correct 1582 ms 45516 KB Ok
92 Correct 1501 ms 45280 KB Ok
93 Correct 1637 ms 45376 KB Ok
94 Correct 1697 ms 45204 KB Ok
95 Correct 1722 ms 45308 KB Ok
96 Execution timed out 2070 ms 50084 KB Time limit exceeded
97 Halted 0 ms 0 KB -