제출 #1165140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165140		chikien2009	Arranging Shoes (IOI19_shoes)	C++20	컴파일 에러	0 ms	0 KiB

shoes

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

using namespace std;

// inline void setup()
// {
// #ifndef ONLINE_JUDGE
//     freopen("test.inp", "r", stdin);
//     freopen("test.out", "w", stdout);
// #endif
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);
// }

class FENWICK_TREE
{
private:
    long long tree_size;
    vector<long long> tree;

public:
    FENWICK_TREE(long long new_size)
    {
        tree_size = new_size;
        tree.resize(tree_size + 1, 0);
    }
    void Update(long long pos, long long val)
    {
        while (pos <= tree_size)
        {
            tree[pos] += val;
            pos += pos & (~(pos - 1));
        }
    }
    long long Get(long long pos)
    {
        long long res = 0;
        while (0 < pos)
        {
            res += tree[pos];
            pos -= pos & (~(pos - 1));
        }
        return res;
    }
};

long long count_swaps(vector<long long> S)
{
    long long a, b, c, d;
    vector<long long> v;
    set<long long> p;
    long long res = 0;
    queue<long long> neg[S.size() / 2 + 1], pos[S.size() / 2 + 1];
    FENWICK_TREE ft(S.size());
    S.insert(S.begin(), 0);
    for (long long i = 1; i < S.size(); ++i)
    {
        if (S[i] < 0)
        {
            neg[-S[i]].push(i);
            p.insert(i);
        }
        else
        {
            pos[S[i]].push(i);
        }
    }
    for (long long i = 1, j = 1; i < S.size(); ++i)
    {
        while (j < S.size() && S[j] == 0)
        {
            j++;
        }
        if (!(i & 1))
        {
            if (-v.back() == S[j])
            {
                v.push_back(S[j]);
                j++;
                continue;
            }
            a = pos[-v.back()].front();
            res += a - j - (ft.Get(a) - ft.Get(j - 1));
            ft.Update(a, 1);
            pos[-v.back()].pop();
            v.push_back(S[a]);
            S[a] = 0;
        }
        else
        {
            if (S[j] < 0)
            {
                neg[-S[j]].pop();
                v.push_back(S[j]);
                p.erase(j);
                j++;
                continue;
            }
            a = *p.begin();
            res += a - j - (ft.Get(a) - ft.Get(j - 1));
            ft.Update(a, 1);
            neg[S[a]].pop();
            p.erase(a);
            v.push_back(S[a]);
            S[a] = 0;
        }
    }
    return res;
}

// long long main()
// {
//     setup();

//     long long n;
//     vector<long long> v;
//     cin >> n;
//     v.resize(n);
//     for (long long i = 0; i < n; ++i)
//     {
//         cin >> v[i];
//     }
//     cout << count_swap(v);
//     return 0;
// }

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

/usr/bin/ld: /tmp/ccu2kcJO.o: in function `main':
grader.cpp:(.text.startup+0x289): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status