oj.uz

Submission #601941

# Submission time Handle Problem Language Result Execution time Memory
601941 2022-07-22T12:46:09 Z JeanBombeur Boarding Passes (BOI22_passes) C++17
100 / 100
 1848 ms 14556 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

//  <|°_°|>

//  M. Broccoli

const int MAX_GROUPS = (15);
const int MAX_PASSENGERS = (1e5 + 1);
const int LOG = 16;


long long DP[1 << MAX_GROUPS];
vector <long long> Cost[MAX_GROUPS][MAX_GROUPS];

char Passengers[MAX_PASSENGERS];

vector <int> Seats[MAX_GROUPS];

int nbPassengers;

void Read() {
    scanf("%s", Passengers);
    nbPassengers = strlen(Passengers);
    for (int i = 0; i < nbPassengers; i ++)
    {
        Seats[Passengers[i] - 'A'].push_back(i);
    }
    return;
}

long long NbLeft(int group, int seat) {
    int pos = -1;
    int sz = Seats[group].size();
    for (int jump = 1 << LOG; jump; jump >>= 1)
    {
        if (pos + jump < sz && Seats[group][pos + jump] < seat)
            pos += jump;
    }
    return ++ pos;
}

long long NbRight(int group, int seat) {
    return Seats[group].size() - NbLeft(group, seat);
}

void Setup() {
    for (int set = 0; set < MAX_GROUPS; set ++)
    {
        for (int nouv = 0; nouv < MAX_GROUPS; nouv ++)
        {
            int sz = Seats[nouv].size();
            long long sum = 0;
            for (int i = 0; i < sz; i ++)
            {
                sum += NbRight(set, Seats[nouv][i]);
            }
            Cost[set][nouv].push_back(sum);
            for (int cut = 0; cut < sz; cut ++)
            {
                sum += NbLeft(set, Seats[nouv][cut]) - NbRight(set, Seats[nouv][cut]);
                Cost[set][nouv].push_back(sum);
            }
        }
    }
    return;
}

bool GoLeft(int mask, int group, int cut) {
    int sz = Seats[group].size();
    int cur = Seats[group][cut];
    long long left = cut, right = sz - cut - 1;
    for (int i = 0; i < MAX_GROUPS; i ++)
    {
        if ((mask >> i) & 1)
        {
            left += 2 * NbLeft(i, cur);
            right += 2 * NbRight(i, cur);
        }
    }
    return left < right;
}

int FindCut(int mask, int group) {
    int cut = -1;
    int sz = Seats[group].size();
    for (int jump = 1 << LOG; jump; jump >>= 1)
    {
        if (cut + jump < sz && GoLeft(mask, group, cut + jump))
            cut += jump;
    }
    return ++ cut;
}

long long CostTransi(int mask, int group) {
    long long sum = 0;
    long long sz = Seats[group].size();
    long long cut = FindCut(mask, group);
    for (int i = 0; i < MAX_GROUPS; i ++)
    {
        if ((mask >> i) & 1)
            sum += 2 * Cost[i][group][cut];
    }
    sum += (cut * (cut - 1)) / 2 + ((sz - cut) * (sz - cut - 1)) / 2;
    return sum;
}

void Solve() {
    fill_n(DP, 1 << MAX_GROUPS, 1LL << 60);
    DP[0] = 0;
    for (int mask = 0; mask < (1 << MAX_GROUPS); mask ++)
    {
        for (int i = 0; i < MAX_GROUPS; i ++)
        {
            if (!((mask >> i) & 1))
                DP[mask ^ (1 << i)] = min(DP[mask ^ (1 << i)], DP[mask] + CostTransi(mask, i));
        }
    }
    printf("%lld", DP[(1 << MAX_GROUPS) - 1] / 2);
    if (DP[(1 << MAX_GROUPS) - 1] & 1)
        printf(".5");
    printf("\n");
    return;
}

int main() {
    Read();
    Setup();
    Solve();
    return 0;
}

Compilation message

passes.cpp: In function 'void Read()':
passes.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%s", Passengers);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 692 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 18 ms 580 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 23 ms 580 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 27 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 58 ms 684 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 169 ms 10788 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 170 ms 12652 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 175 ms 13416 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 175 ms 13380 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 49 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 160 ms 572 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 134 ms 572 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 78 ms 568 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 62 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 149 ms 584 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 93 ms 552 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 102 ms 556 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 105 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 97 ms 560 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 121 ms 568 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 102 ms 572 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 100 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 90 ms 564 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 117 ms 560 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 97 ms 560 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 49 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 160 ms 572 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 134 ms 572 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 78 ms 568 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 62 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 149 ms 584 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 93 ms 552 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 102 ms 556 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 105 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 97 ms 560 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 121 ms 568 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 102 ms 572 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 100 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 90 ms 564 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 117 ms 560 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 97 ms 560 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 37 ms 556 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 44 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 171 ms 588 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 134 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 76 ms 584 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 58 ms 556 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 148 ms 572 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 100 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 114 ms 564 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 99 ms 588 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 95 ms 560 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 93 ms 556 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 106 ms 556 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 100 ms 576 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 86 ms 556 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 91 ms 568 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 93 ms 564 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 85 ms 1908 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 86 ms 1952 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 594 ms 2044 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 473 ms 1816 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 135 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 563 ms 1820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 610 ms 2228 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 561 ms 2268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 603 ms 2132 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 557 ms 2132 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 572 ms 2252 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 568 ms 2244 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 692 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 18 ms 580 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 23 ms 580 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 27 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 58 ms 684 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 169 ms 10788 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 170 ms 12652 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 175 ms 13416 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 175 ms 13380 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 39 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 49 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 160 ms 572 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 134 ms 572 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 78 ms 568 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 62 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 149 ms 584 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 93 ms 552 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 102 ms 556 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 105 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 97 ms 560 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 121 ms 568 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 102 ms 572 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 100 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 90 ms 564 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 117 ms 560 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 97 ms 560 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 37 ms 556 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 44 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 171 ms 588 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 134 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 76 ms 584 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 58 ms 556 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 148 ms 572 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 100 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 114 ms 564 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 99 ms 588 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 95 ms 560 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 93 ms 556 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 106 ms 556 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 100 ms 576 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 86 ms 556 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 91 ms 568 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 93 ms 564 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 85 ms 1908 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 86 ms 1952 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 594 ms 2044 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 473 ms 1816 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 135 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 563 ms 1820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 610 ms 2228 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 561 ms 2268 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 603 ms 2132 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 557 ms 2132 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 572 ms 2252 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 568 ms 2244 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 59 ms 468 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 168 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 58 ms 692 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 17 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 27 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 27 ms 580 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 66 ms 596 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 155 ms 10868 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 166 ms 12604 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 182 ms 13400 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 217 ms 13332 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 41 ms 552 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 44 ms 572 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 166 ms 576 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 132 ms 564 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 76 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 57 ms 556 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 139 ms 572 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 91 ms 556 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 97 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 101 ms 560 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 93 ms 556 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 94 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 115 ms 556 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 113 ms 556 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 86 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 91 ms 564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 92 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 97 ms 1976 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 91 ms 1876 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 587 ms 2004 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 481 ms 1812 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 133 ms 1872 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 556 ms 1832 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 613 ms 2224 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 569 ms 2264 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 593 ms 2132 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 589 ms 2136 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 566 ms 2180 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 600 ms 2260 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1626 ms 13944 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 166 ms 560 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 988 ms 13888 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 250 ms 13440 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 105 ms 552 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 1580 ms 14028 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 1701 ms 14156 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 1660 ms 14144 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 1790 ms 14140 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 1714 ms 14232 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 1653 ms 14220 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 1651 ms 14260 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 1530 ms 13980 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 1848 ms 14556 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'