Submission #408754

#	Time	Username	Problem	Language	Result	Execution time	Memory
408754		idk321	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1099 ms	9828 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;

    vector<int> sumRight(2 * n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {

        if (s[i - 1] > 0)sumRight[i]++;
        sumRight[i] += sumRight[i - 1];
    }



    for (int i = 0; i < 2 * n; i++)
    {

        if (s[i] < 0)
        {
            if (match[i] > i)
            {
                res += sumRight[match[i]] - sumRight[i];
            } else
            {
                res += sumRight[i] - sumRight[match[i]];
            }
        }
    }



    for (int i = 0; i < 2 * n; i++)
    {
        for (int j = i + 1; j < 2 * n; j++)
        {
            if (s[i] < 0 && s[j] < 0)
            {
                array<int, 2> ival1 = {min(match[i], i), max(match[i], i)};
                array<int, 2> ival2 = {min(match[j], j), max(match[j], j)};
                if (ival1[0] >= ival2[0] && ival1[1] <= ival2[1])
                {
                    res++;
                    continue;
                }
                if (ival2[0] >= ival1[0] && ival2[1] <= ival1[1])
                {
                    res++;
                    continue;
                }

                int d1 = match[i] - i;
                int d2 = match[j] - j;
                if (d1 > 0 && d2 < 0 || d1 < 0 && d2 > 0)
                {
                    if (!(ival1[1] < ival2[0] || ival1[0] > ival2[1]))
                    {
                        res++;
                        continue;
                    }
                }
            }
        }
    }



    /*
    vector<array<int,2 >> rivals;
    vector<array<int, 2>> livals;
    for (int i = 0; i < 2 * n; i++)
    {

        if (s[i] < 0)
        {
            if (match[i] > i) rivals.push_back({i, match[i]});
            else livals.push_back({match[i], i});
        }
    }

    for (auto c1 : rivals)
    {
        for (auto c2 : livals)
        {
            if (!(c2[1] < c1[0] || c2[0] > c1[1])) res++;
        }
    }

    for (int i = 0; i < 4 * N; i++) tree[i] = 0;

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

    for (int i = 0; i < 4 * N; i++) tree[i] = 0;

    for (int i = 2 * n - 1; i >= 0; i--)
    {
        if (s[i] < 0 && match[i] < i)
        {
            res += getSum(0, match[i], 0, N - 1, 1);
            ins(1, 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++)
      |                     ~~^~~~~~~~~~
shoes.cpp:110:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  110 |                 if (d1 > 0 && d2 < 0 || d1 < 0 && d2 > 0)
      |                     ~~~~~~~^~~~~~~~~

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