oj.uz

Submission #543828

# Submission time Handle Problem Language Result Execution time Memory
543828 2022-03-31T13:34:04 Z Tien_Noob Arranging Shoes (IOI19_shoes) C++17
10 / 100
 6 ms 9700 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 2e5;
vector<int> id[N + 1][2];
struct FenwickTree
{
    int Tree[N + 1];
    void add(int pos, int val)
    {
        for (; pos <= N; pos += (pos & (-pos)))
        {
            Tree[pos] += val;
        }
    }
    int sum(int pos)
    {
        int ret = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
        {
            ret += Tree[pos];
        }
        return ret;
    }
    int sum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
} Tree;
long long count_swaps(vector<int> a)
{
    long long res = 0;
    int n = a.size();
    a.insert(a.begin(), 0);
    for (int i = 1; i <= n; ++ i)
    {
        int x = (a[i] < 0) ? 0 : 1;
        int b = abs(a[i]);
        if (!id[abs(a[i])][1 ^ x].empty())
        {
            int r = i + Tree.sum(i), l = id[b][1 ^ x].back() + Tree.sum(id[b][1 ^ x].back());
            res += r - l - (a[i] > 0);
            //cerr << r - l - (a[i] > 0) << '\n';
            Tree.add(i, -1);
            Tree.add(id[b][1 ^ x].back() + (a[i] < 0), 1);
            id[b][1 ^ x].pop_back();
        }
        else
        {
            id[b][x].push_back(i);
        }
    }
    return res;
}
/*void read()
{
    cout << count_swaps({2, 1, -1, -2});
}
void solve()
{

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9696 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9696 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9700 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Incorrect 5 ms 9700 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9696 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9696 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9700 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Incorrect 5 ms 9700 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9696 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9696 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9700 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Incorrect 5 ms 9700 KB Output isn't correct
15 Halted 0 ms 0 KB -