oj.uz

Submission #591089

# Submission time Handle Problem Language Result Execution time Memory
591089 2022-07-06T20:26:38 Z dryeab Arranging Shoes (IOI19_shoes) C++17
10 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

struct segment_tree {

    int n;
    vector<int> tree;

    void init(int i) {
        n = 1;
        while (n < i)
            n <<= 1;
        tree.resize(n, 0);
        
    }

    void set(int i) {
        i += n;
        tree[i] = 1;

        for (i /= 2; i > 0; i /= 2)
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    int get(int l, int r) {
        int res = 0;
        while (l <= r) {
            if (l & 1)
                res += tree[l++];
            if (!(r & 1))
                res += tree[r--];
            r /= 2, l /= 2;
        }
        return res;
    }
};

long long count_swaps(vector<int> s) {

    int n = s.size(), shift = 0;

    vector<vector<int>> left(n / 2 + 1), right(n / 2 + 1);
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] < 0)
            left[-s[i]].push_back(i);
        else
            right[s[i]].push_back(i);
    }

    long long res = 0;

    segment_tree st;
    st.init(n);

    for (int i = 0, j; i < n; ++i) {

        if (s[i] == 0) {
            // shift--;
            continue;

        } else if (s[i] > 0) {

            j = left[s[i]][left[s[i]].size() - 1];
            left[s[i]].pop_back();
            right[s[i]].pop_back();

            shift = st.get(i + 1, j - 1);
            res += j - i - shift;
            s[j] = s[i] = 0;

            st.set(i), st.set(j);
        } else {

            j = right[-s[i]][right[-s[i]].size() - 1];
            right[-s[i]].pop_back();
            left[-s[i]].pop_back();

            shift = st.get(i + 1, j - 1);

            res += j - i - shift - 1;

            s[j] = s[i] = 0;
            st.set(i), st.set(j);
        }

        // shift++;
    }

    return res;
}

// int main() {

//     ios::sync_with_stdio(false);
//     cin.tie(0);

//     int n;
//     cin >> n;

//     vector<int> s(n);
//     for (int &i : s)
//         cin >> i;

//     cout <<  count_swaps(s) << endl;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -