oj.uz

Submission #1036862

# Submission time Handle Problem Language Result Execution time Memory
1036862 2024-07-27T18:07:27 Z anango Boarding Passes (BOI22_passes) C++17
100 / 100
 1561 ms 252932 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define o 0
#define push_front push_back
int INF = 1LL<<62;
 
void solve() {
 
    string S; cin >> S;
    int n = S.size();
    vector<int> ar(n); for (int i=0; i<n; i++) ar[i] = (S[i]-'A');
    int G = *max_element(ar.begin(), ar.end()); G++;
    int pref[n+1][G]; //count of character c, before index i
    int suff[n+1][G]; //count of character c, after or equal to index i
    for (int i=0; i<=n; i++) {
        for (int j=0; j<G; j++) {
            pref[i][j] = suff[i][j] = 0;
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<G; j++) {
            if (j==ar[i]) {
                pref[i+1][j] = pref[i][j]+1;
            }
            else {
                pref[i+1][j] = pref[i][j];
            }
        }
    }
    
    for (int i=n-1; i>=0; i--) {
        for (int j=0; j<G; j++) {
            if (j==ar[i]) {
                suff[i][j] = suff[i+1][j]+1;
            }
            else {
                suff[i][j] = suff[i+1][j];
            }
        }
    }
    //everyone before L boards from the front, everyone after or equal to it boards from the back. 
    vector<vector<int>> counts(G,vector<int>(G,0));     //counts[i][j] = sum of subsequences of (i,j) before l, and subsequences of (j,i) after L
    //counts[i][j] = sum of pref[k][j] for k<=L and ar[k]=i, and analogous expression for the suffix
    //first, get initial count values (for everyone boarding from the back)
    //and assuming that these are already boarded since the back breaker may not be the same for each group - that was false assumption
    //so precomp counts then ternary search on the breakpoint
    for (int j=0; j<G; j++) {
        for (int k=0; k<n; k++) {
            int i = ar[k];
            //cout << "adding " << i <<" " << j <<" " << k <<" " << j << " " << suff[k][j] << endl;
            counts[i][j] += suff[k+1][j];
        }
    }
    vector<vector<vector<int>>> acounts;
    acounts.push_back(counts);
    for (int L=0; L<n; L++) {
 
        //counts[i][j] = number of swaps required if i goes after j
 
 
 
        //transfer L to the right
        int cur = ar[L];
        for (int j=0; j<G; j++) {
            int delta = suff[L+1][j];
            int delta2 = pref[L][j];
            counts[cur][j] -= delta-delta2;
        }
        acounts.push_back(counts);
        
        /*cout << "TRANSFERRED TO " << L+1 << endl;
        for (int i=0; i<G; i++) {
            for (int j=0; j<G; j++) {
                cout << i <<" " << j <<" " << counts[i][j] << endl;
            }
        }
        cout << endl;*/
    }
    //acounts[breakpoint][group_1][group_2]
    //ABCABCAA

    vector<int> dp;
    vector<vector<int>> indices(G);
    for (int i=0; i<n; i++) {
        indices[ar[i]].push_back(i);
    }
    for (int i=0; i<G; i++) {
        if (indices[i].size()==0) continue;
        if (indices[i].front()!=0) indices[i].push_front(0);
        if (indices[i].back()!=n-1) {
            indices[i].push_back(n-1);
        }
    }
    for (int i=0; i<G; i++) {
        sort(indices[i].begin(), indices[i].end());
    }
    dp=vector<int>(1<<G,INF); //dp[mask] = min cost if this mask is at the beginning of the ordering
    dp[0] = 0;
    for (int mask=0; mask<1<<G; mask++) {
        for (int addon=0; addon<G; addon++) {
            if (mask&(1<<addon)) continue;
            if (indices[addon].size()==0) { 
                dp[mask | (1<<addon)] = min(dp[mask | (1<<addon)],dp[mask]+o);
                continue;
            }
            int l = 0; int r = indices[addon].size(); r--;
            int mi = 1LL<<62;
            while (l<r-1) {
                //cout << l << " " << r << endl;
                //cout << indices[addon][l] <<" " << indices[addon][r] << endl;
                int m1,m2;
                if (r-l>30) {
                    m1 = l+(r-l)/9;
                    m2 = r-(r-l)/9;
                }
                else {
                    m1 = l;
                    m2 = r;
                }
                int am1 = 0;
                for (int j=0; j<G; j++) {
                    if (mask&(1<<j)) {
                        am1+=2*acounts[indices[addon][m1]][addon][j];
                    }
                    if (j==addon) {
                        am1+=acounts[indices[addon][m1]][addon][j];
                    }
                }
                int am2 = 0;
                for (int j=0; j<G; j++) {
                    if (mask&(1<<j)) {
                        am2+=2*acounts[indices[addon][m2]][addon][j];
                    }
                    if (j==addon) {
                        am2+=acounts[indices[addon][m2]][addon][j];
                    }
                }
                mi = min(mi,min(am1,am2));
                //cout << "adding " << mask <<" " << addon <<" " << l <<" " << r <<" " << m1 <<" " << m2 <<" " << am1 <<" " << am2 << endl;
                if (am1>am2) {
                    l=m1+1; r=r;
                }
                else if (am1<am2) {
                    l=l; r=m2-1;
                }
                else {
                    l=m1+1; r=m2;
                }
                //cout << mask <<" " << addon <<" " << al <<endl;
            }
            int al = 0;
            for (int j=0; j<G; j++) {
                if (mask&(1<<j)) {
                    al+=2*acounts[indices[addon][l]][addon][j];
                }
                if (j==addon) {
                    al+=acounts[indices[addon][l]][addon][j];
                }
            }
            dp[mask | (1<<addon)] = min(dp[mask | (1<<addon)],dp[mask]+al);
            if (l+1==indices[addon].size()) {
                continue;
            }
            al = 0;
            for (int j=0; j<G; j++) {
                if (mask&(1<<j)) {
                    al+=2*acounts[indices[addon][l+1]][addon][j];
                }
                if (j==addon) {
                    al+=acounts[indices[addon][l+1]][addon][j];
                }
            }
            dp[mask | (1<<addon)] = min(dp[mask | (1<<addon)],dp[mask]+al);
        }
    }
    int ans=dp[(1<<G)-1];
 
    int a2 = ans/2;
    cout << a2;
    if (ans%2==1) cout << ".50";
    cout << endl;
}
 
signed main() {
    int local=0;
    if (local) {
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    }
    /*#ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif*/ //fast IO
    solve();
    
}

Compilation message

passes.cpp: In function 'void solve()':
passes.cpp:162:20: 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]
  162 |             if (l+1==indices[addon].size()) {
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passes.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 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 15 ms 10764 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 16 ms 12556 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 19 ms 13420 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 22 ms 13324 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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 0 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 432 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 436 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 8 ms 10348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 8 ms 10308 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 21 ms 14228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 18 ms 14232 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 12 ms 14232 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 20 ms 14232 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 19 ms 13856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 21 ms 13976 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 19 ms 13976 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 20 ms 14072 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 20 ms 13976 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 20 ms 13976 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 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 15 ms 10764 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 16 ms 12556 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 19 ms 13420 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 22 ms 13324 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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 0 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 432 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 ms 436 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 8 ms 10348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 8 ms 10308 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 21 ms 14228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 18 ms 14232 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 12 ms 14232 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 20 ms 14232 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 19 ms 13856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 21 ms 13976 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 19 ms 13976 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 20 ms 14072 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 20 ms 13976 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 20 ms 13976 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 28 ms 600 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 69 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 13 ms 11016 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 15 ms 12596 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 17 ms 13320 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 17 ms 13324 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 344 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 456 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 436 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 9 ms 10500 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 8 ms 10392 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 21 ms 14228 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 18 ms 14340 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 12 ms 14232 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 19 ms 14228 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 20 ms 13976 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 20 ms 13976 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 20 ms 14100 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 20 ms 13972 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 19 ms 13976 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 20 ms 14100 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1561 ms 252440 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 44 ms 852 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 1018 ms 252164 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 264 ms 252932 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 53 ms 928 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 990 ms 252444 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 1381 ms 252420 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 1245 ms 251584 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 1301 ms 251620 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 1289 ms 251408 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 1186 ms 251556 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 1327 ms 251780 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 662 ms 235508 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 1385 ms 251664 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'