제출 #473082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
473082		blue	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	80 ms	11960 KiB

shoes

#include "shoes.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 100'000;
vector<int> A[1+maxN];
vector<int> B[1+maxN];
vector<int> actpos;

long long count_swaps(vector<int> S)
{
    int N = (int)S.size()/2;

    for(int i = 0; i < 2*N; i++)
    {
        if(S[i] < 0)
            A[ -S[i] ].push_back(i);
        else
            B[ S[i] ].push_back(i);
    }

    vector< pair<int, int> > X;
    for(int s = 1; s <= N; s++)
    {
        for(int i = 0; i < A[s].size(); i++)
            X.push_back(make_pair(A[s][i], B[s][i]));
    }

    actpos = vector<int>(2*N);

    int ct = -1;
    for(pair<int, int> x: X)
    {
        actpos[ x.first ] = ++ct;
        actpos[ x.second ] = ++ct;
    }

    long long res = 0;
    vector<int> a_sort(2*N);
    for(int i = 0; i < 2*N; i++) a_sort[i] = i;
    sort(a_sort.begin(), a_sort.end(), [] (int u, int v)
    {
        return actpos[u] > actpos[v];
    });

    vector<int> BIT(1+2*N, 0);
    for(int g: a_sort)
    {
        for(int i = g+1 - 1; i >= 1; i -= i&-i)
            res += BIT[i];

        for(int i = g+1; i <= 2*N; i += i&-i)
            BIT[i]++;
    }
    return res;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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