oj.uz

Submission #159202

# Submission time Handle Problem Language Result Execution time Memory
159202 2019-10-21T13:16:52 Z Bilyana Arranging Shoes (IOI19_shoes) C++17
65 / 100
 240 ms 142848 KB 
#include<iostream>
#include<queue>
#include<cmath>

using namespace std;

const long long MAXN = 200000;
long long n, to[MAXN+10], from[MAXN+10];
queue<long long> bs[MAXN+10];
long long fw[MAXN+10];
long long counter=0;

void find_place(vector<int> S)
{
    long long curr = 0;
    long long temp;
    for (long long i=0; i<n; i++)
    {
        temp = abs(S[i]);
        if (S[i]>0)
        {
            if (!bs[temp].empty() && bs[temp].front()%2==0)
            {
                to[i] = bs[temp].front()+1;
                bs[temp].pop();
            }
            else
            {
                to[i] = curr+1;
                bs[temp].push(curr+1);
                curr += 2;
            }
        }
        else
        {
            if (!bs[temp].empty() && bs[temp].front()%2==1)
            {
                to[i] = bs[temp].front()-1;
                bs[temp].pop();
            }
            else
            {
                to[i] = curr;
                bs[temp].push(curr);
                curr += 2;
            }
        }
    }
}

void calc_from()
{
    for (long long i=0; i<n; i++)
    {
        from[to[i]] = i;
    }
}

void update(long long curr, long long dif)
{
    curr++;
    while(curr>0)
    {
        fw[curr] += dif;
        curr -= (curr&(-curr));
    }
}

long long sum(long long curr)
{
    curr++;
    long long sm = 0;
    while (curr<MAXN)
    {
        sm += fw[curr];
        curr += (curr&(-curr));
    }
    return sm;
}

void sorting()
{
    for (long long i=0; i<n; i++)
    {
        long long curr = sum(from[i]) + from[i];
        counter += abs(curr-i);
        update(from[i],1);
    }
}

void solve(vector<int> S)
{
    n = S.size();
    find_place(S);
    calc_from();
    sorting();
}

long long count_swaps(vector<int> S)
{
    solve(S);
    return counter;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 134904 KB Output is correct
2 Correct 135 ms 134908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 134904 KB Output is correct
2 Correct 135 ms 134908 KB Output is correct
3 Correct 135 ms 134968 KB Output is correct
4 Correct 134 ms 135000 KB Output is correct
5 Correct 135 ms 134968 KB Output is correct
6 Correct 135 ms 134972 KB Output is correct
7 Correct 136 ms 135032 KB Output is correct
8 Correct 135 ms 135032 KB Output is correct
9 Correct 137 ms 134904 KB Output is correct
10 Correct 135 ms 135032 KB Output is correct
11 Correct 138 ms 134916 KB Output is correct
12 Correct 135 ms 134904 KB Output is correct
13 Correct 135 ms 135032 KB Output is correct
14 Correct 135 ms 134908 KB Output is correct
15 Correct 152 ms 135144 KB Output is correct
16 Correct 135 ms 134904 KB Output is correct
17 Correct 135 ms 134976 KB Output is correct
18 Correct 136 ms 134900 KB Output is correct
19 Correct 134 ms 135004 KB Output is correct
20 Correct 137 ms 135056 KB Output is correct
21 Correct 134 ms 134904 KB Output is correct
22 Correct 134 ms 134984 KB Output is correct
23 Correct 134 ms 134904 KB Output is correct
24 Correct 134 ms 135004 KB Output is correct
25 Correct 135 ms 135144 KB Output is correct
26 Correct 135 ms 135012 KB Output is correct
27 Correct 134 ms 135032 KB Output is correct
28 Correct 136 ms 134972 KB Output is correct
29 Correct 134 ms 134904 KB Output is correct
30 Correct 135 ms 135060 KB Output is correct
31 Correct 135 ms 135032 KB Output is correct
32 Correct 134 ms 135032 KB Output is correct
33 Correct 135 ms 135032 KB Output is correct
34 Correct 139 ms 134904 KB Output is correct
35 Correct 135 ms 135168 KB Output is correct
36 Correct 136 ms 135036 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 134904 KB Output is correct
2 Correct 135 ms 134908 KB Output is correct
3 Correct 135 ms 134984 KB Output is correct
4 Correct 135 ms 135004 KB Output is correct
5 Correct 137 ms 134996 KB Output is correct
6 Correct 138 ms 134980 KB Output is correct
7 Correct 136 ms 134904 KB Output is correct
8 Correct 135 ms 134980 KB Output is correct
9 Correct 134 ms 135008 KB Output is correct
10 Correct 134 ms 135008 KB Output is correct
11 Correct 134 ms 134904 KB Output is correct
12 Correct 136 ms 135028 KB Output is correct
13 Correct 135 ms 134964 KB Output is correct
14 Correct 134 ms 134904 KB Output is correct
15 Correct 140 ms 135000 KB Output is correct
16 Correct 147 ms 135032 KB Output is correct
17 Correct 137 ms 135004 KB Output is correct
18 Correct 145 ms 135032 KB Output is correct
19 Correct 147 ms 135036 KB Output is correct
20 Correct 150 ms 136028 KB Output is correct
21 Correct 148 ms 135804 KB Output is correct
22 Correct 186 ms 142064 KB Output is correct
23 Correct 173 ms 142028 KB Output is correct
24 Correct 191 ms 142152 KB Output is correct
25 Correct 188 ms 142820 KB Output is correct
26 Correct 216 ms 142080 KB Output is correct
27 Incorrect 173 ms 142056 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 135072 KB Output is correct
2 Correct 136 ms 135004 KB Output is correct
3 Correct 135 ms 135140 KB Output is correct
4 Correct 136 ms 135016 KB Output is correct
5 Correct 197 ms 142056 KB Output is correct
6 Correct 194 ms 142040 KB Output is correct
7 Correct 198 ms 142052 KB Output is correct
8 Correct 185 ms 142848 KB Output is correct
9 Correct 216 ms 142184 KB Output is correct
10 Correct 240 ms 142028 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 134904 KB Output is correct
2 Correct 135 ms 134908 KB Output is correct
3 Correct 135 ms 134968 KB Output is correct
4 Correct 134 ms 135000 KB Output is correct
5 Correct 135 ms 134968 KB Output is correct
6 Correct 135 ms 134972 KB Output is correct
7 Correct 136 ms 135032 KB Output is correct
8 Correct 135 ms 135032 KB Output is correct
9 Correct 137 ms 134904 KB Output is correct
10 Correct 135 ms 135032 KB Output is correct
11 Correct 138 ms 134916 KB Output is correct
12 Correct 135 ms 134904 KB Output is correct
13 Correct 135 ms 135032 KB Output is correct
14 Correct 135 ms 134908 KB Output is correct
15 Correct 152 ms 135144 KB Output is correct
16 Correct 135 ms 134904 KB Output is correct
17 Correct 135 ms 134976 KB Output is correct
18 Correct 136 ms 134900 KB Output is correct
19 Correct 134 ms 135004 KB Output is correct
20 Correct 137 ms 135056 KB Output is correct
21 Correct 134 ms 134904 KB Output is correct
22 Correct 134 ms 134984 KB Output is correct
23 Correct 134 ms 134904 KB Output is correct
24 Correct 134 ms 135004 KB Output is correct
25 Correct 135 ms 135144 KB Output is correct
26 Correct 135 ms 135012 KB Output is correct
27 Correct 134 ms 135032 KB Output is correct
28 Correct 136 ms 134972 KB Output is correct
29 Correct 134 ms 134904 KB Output is correct
30 Correct 135 ms 135060 KB Output is correct
31 Correct 135 ms 135032 KB Output is correct
32 Correct 134 ms 135032 KB Output is correct
33 Correct 135 ms 135032 KB Output is correct
34 Correct 139 ms 134904 KB Output is correct
35 Correct 135 ms 135168 KB Output is correct
36 Correct 136 ms 135036 KB Output is correct
37 Correct 163 ms 134904 KB Output is correct
38 Correct 136 ms 135004 KB Output is correct
39 Correct 139 ms 135084 KB Output is correct
40 Correct 136 ms 134944 KB Output is correct
41 Correct 136 ms 135032 KB Output is correct
42 Correct 135 ms 135032 KB Output is correct
43 Correct 136 ms 135028 KB Output is correct
44 Correct 150 ms 135088 KB Output is correct
45 Correct 162 ms 135032 KB Output is correct
46 Correct 135 ms 135060 KB Output is correct
47 Correct 134 ms 135032 KB Output is correct
48 Correct 134 ms 135040 KB Output is correct
49 Correct 154 ms 134980 KB Output is correct
50 Correct 179 ms 135032 KB Output is correct
51 Correct 148 ms 135128 KB Output is correct
52 Correct 146 ms 135004 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 134904 KB Output is correct
2 Correct 135 ms 134908 KB Output is correct
3 Correct 135 ms 134968 KB Output is correct
4 Correct 134 ms 135000 KB Output is correct
5 Correct 135 ms 134968 KB Output is correct
6 Correct 135 ms 134972 KB Output is correct
7 Correct 136 ms 135032 KB Output is correct
8 Correct 135 ms 135032 KB Output is correct
9 Correct 137 ms 134904 KB Output is correct
10 Correct 135 ms 135032 KB Output is correct
11 Correct 138 ms 134916 KB Output is correct
12 Correct 135 ms 134904 KB Output is correct
13 Correct 135 ms 135032 KB Output is correct
14 Correct 135 ms 134908 KB Output is correct
15 Correct 152 ms 135144 KB Output is correct
16 Correct 135 ms 134904 KB Output is correct
17 Correct 135 ms 134976 KB Output is correct
18 Correct 136 ms 134900 KB Output is correct
19 Correct 134 ms 135004 KB Output is correct
20 Correct 137 ms 135056 KB Output is correct
21 Correct 134 ms 134904 KB Output is correct
22 Correct 134 ms 134984 KB Output is correct
23 Correct 134 ms 134904 KB Output is correct
24 Correct 134 ms 135004 KB Output is correct
25 Correct 135 ms 135144 KB Output is correct
26 Correct 135 ms 135012 KB Output is correct
27 Correct 134 ms 135032 KB Output is correct
28 Correct 136 ms 134972 KB Output is correct
29 Correct 134 ms 134904 KB Output is correct
30 Correct 135 ms 135060 KB Output is correct
31 Correct 135 ms 135032 KB Output is correct
32 Correct 134 ms 135032 KB Output is correct
33 Correct 135 ms 135032 KB Output is correct
34 Correct 139 ms 134904 KB Output is correct
35 Correct 135 ms 135168 KB Output is correct
36 Correct 136 ms 135036 KB Output is correct
37 Correct 135 ms 134984 KB Output is correct
38 Correct 135 ms 135004 KB Output is correct
39 Correct 137 ms 134996 KB Output is correct
40 Correct 138 ms 134980 KB Output is correct
41 Correct 136 ms 134904 KB Output is correct
42 Correct 135 ms 134980 KB Output is correct
43 Correct 134 ms 135008 KB Output is correct
44 Correct 134 ms 135008 KB Output is correct
45 Correct 134 ms 134904 KB Output is correct
46 Correct 136 ms 135028 KB Output is correct
47 Correct 135 ms 134964 KB Output is correct
48 Correct 134 ms 134904 KB Output is correct
49 Correct 140 ms 135000 KB Output is correct
50 Correct 147 ms 135032 KB Output is correct
51 Correct 137 ms 135004 KB Output is correct
52 Correct 145 ms 135032 KB Output is correct
53 Correct 147 ms 135036 KB Output is correct
54 Correct 150 ms 136028 KB Output is correct
55 Correct 148 ms 135804 KB Output is correct
56 Correct 186 ms 142064 KB Output is correct
57 Correct 173 ms 142028 KB Output is correct
58 Correct 191 ms 142152 KB Output is correct
59 Correct 188 ms 142820 KB Output is correct
60 Correct 216 ms 142080 KB Output is correct
61 Incorrect 173 ms 142056 KB Output isn't correct
62 Halted 0 ms 0 KB -