Submission #408783

#	Time	Username	Problem	Language	Result	Execution time	Memory
408783		idk321	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	152 ms	11424 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n;
const int N = 200005;
int tree[4 * N];

void ins(int num, int i, int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = num;
        return;
    }

    int mid = (a + b) / 2;
    if (i <= mid) ins(num, i, a, mid, node * 2);
    if (i > mid) ins(num,i ,mid + 1, b, node * 2 + 1);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int getSum(int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to) return tree[node];

    int mid = (a + b) / 2;
    int res = 0;
    if (from <= mid) res += getSum(from, to, a, mid, node * 2);
    if (to > mid) res += getSum(from, to, mid + 1, b, node * 2+ 1);

    return res;
}



long long count_swaps(std::vector<int> s) {
    n = s.size() / 2;
    vector<vector<int>> isAt(n + 1);
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] < 0) isAt[abs(s[i])].push_back(i);
    }

    vector<int> match(s.size());
    for (int i = s.size() - 1; i >= 0; i--)
    {
        if (s[i] > 0)
        {
            match[i] = isAt[s[i]].back();
            match[isAt[s[i]].back()] = i;
            isAt[s[i]].pop_back();

        }
    }

    ll res = 0;


    for (int i = 0; i < 2 * n; i++) ins(1, i, 0, N - 1, 1);
    for (int i = 0; i < 2 * n; i++)
    {
        if (match[i] > i)
        {
            if (s[i] > 0)
            {
                res++;
            }

            res += getSum(i + 1, match[i] - 1, 0, N - 1, 1);
            ins(0, i, 0, N - 1, 1);
            ins(0, match[i], 0, N - 1, 1);
        }
    }

	return res;
}

/*
5
1 2 -2 2 -2 -1 3 2 -3 -2
*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15