oj.uz

Submission #1098978

# Submission time Handle Problem Language Result Execution time Memory
1098978 2024-10-10T11:46:58 Z crafticat Boarding Passes (BOI22_passes) C++17
30 / 100
 2000 ms 6668 KB 
#include <bits/stdc++.h>

#include <utility>

using ll = long long;
using namespace std;
#define F0R(i, n) for (ll i= 0; i < n;i++)
template<typename T>
using V = vector<T>;
using vi = V<ll>;
using vvi = V<vi>;
#define pb push_back
using pi = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define f first
#define s second

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class T>
using Tree =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

double add(vi x, Tree<int> &points) {
    long double expected = 0;

    F0R(i, x.size()) {
        int orgLEF = points.order_of_key(x[i]);
        int orgRIG = points.size() - orgLEF;
        double lef = orgLEF + (i / 2.0);
        double rig = orgRIG + (x.size() - i - 1) / 2.0;

        expected += min(lef, rig);
    }
    F0R(i, x.size()) {
        points.insert(x[i]);
    }

    return expected;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    string str; cin >> str;
    set<int> ind;
    vvi groups(26);
    F0R(i, str.size()) {
        int id = str[i] - 'A';
        groups[id].pb(i);
        ind.insert(id);
    }

    vi perm;
    for (auto x : ind)
        perm.pb(x);

    double ans = 1e18;
    do {
        Tree<int> points;
        double expected = 0;
        for (auto x : perm) {
            expected += add(groups[x], points);
        }
        ans = min(ans, expected);
    } while (std::next_permutation(all(perm)));

    cout << fixed << ans;
    return 0;
}

Compilation message

passes.cpp: In function 'double add(vi, Tree<int>&)':
passes.cpp:7:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define F0R(i, n) for (ll i= 0; i < n;i++)
......
   28 |     F0R(i, x.size()) {
      |         ~~~~~~~~~~~                
passes.cpp:28:5: note: in expansion of macro 'F0R'
   28 |     F0R(i, x.size()) {
      |     ^~~
passes.cpp:7:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define F0R(i, n) for (ll i= 0; i < n;i++)
......
   36 |     F0R(i, x.size()) {
      |         ~~~~~~~~~~~                
passes.cpp:36:5: note: in expansion of macro 'F0R'
   36 |     F0R(i, x.size()) {
      |     ^~~
passes.cpp: In function 'int main()':
passes.cpp:7:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define F0R(i, n) for (ll i= 0; i < n;i++)
......
   49 |     F0R(i, str.size()) {
      |         ~~~~~~~~~~~~~              
passes.cpp:49:5: note: in expansion of macro 'F0R'
   49 |     F0R(i, str.size()) {
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 32 ms 5388 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 41 ms 6412 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 44 ms 6668 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 44 ms 6664 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 36 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 34 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 30 ms 460 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 28 ms 436 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 9 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 9 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 9 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 9 ms 456 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 9 ms 456 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 9 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 36 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 34 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 30 ms 460 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 28 ms 436 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 9 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 9 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 9 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 9 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 9 ms 456 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 9 ms 456 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 9 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 452 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 37 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 35 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 33 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 3 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 27 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 456 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 11 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 9 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 8 ms 460 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 9 ms 456 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 9 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 9 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 9 ms 464 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 9 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 9 ms 460 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 2 ms 860 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 860 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2077 ms 860 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 32 ms 5388 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 41 ms 6412 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 44 ms 6668 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 44 ms 6664 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 36 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 34 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 30 ms 460 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 3 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 28 ms 436 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 2 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 9 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 9 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 9 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 9 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 9 ms 456 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 9 ms 452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 9 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 9 ms 456 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 9 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 452 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 37 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 35 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 33 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 3 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 27 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 2 ms 456 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 11 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 9 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 8 ms 460 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 9 ms 456 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 9 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 9 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 9 ms 464 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 9 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 9 ms 460 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 2 ms 860 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 2 ms 860 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2077 ms 860 KB Time limit exceeded
47 Halted 0 ms 0 KB -