제출 #1321518

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

shoes

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

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>


void build(ll l, ll r, ll i, vl& tree){
    if (l == r){
        tree[i] = 1;
        return;
    }
    ll mid = (l+r)/2;
    build(l, mid, 2*i, tree);
    build(mid+1, r, 2*i+1, tree);
    tree[i] = tree[2*i] + tree[2*i+1];
    return;
}

void update(ll l, ll r, ll p, ll i, vl& tree){
    if (l == p && r == p){
        tree[i] = 0;
        return;
    }
    if (p < l || r < p){
        return;
    }
    ll mid = (l+r)/2;
    update(l, mid, p, 2*i, tree);
    update(mid+1, r, p, 2*i+1, tree);
    tree[i] = tree[2*i] + tree[2*i+1];
    return;
}

ll query(ll l, ll r, ll L, ll R, ll i, vl& tree){
    if (L <= l && r <= R){
        return tree[i];
    }
    if (r < L || R < l){
        return 0;
    }
    ll mid = (l+r)/2;
    ll a = query(l, mid, L, R, 2*i, tree);
    ll b = query(mid+1, r, L, R, 2*i+1, tree);
    return a + b;
}

ll count_swaps(vl S){
    ll n = S.size();

    vl nums;
    for (ll i = 0; i < n; i++){nums.push_back(S[i]);}

    vll occ (n/2+1);
    vl pairs (n);
    for (ll i = 0; i < n; i++){
        ll p = nums[i];
        if (occ[p].empty()){
            occ[p].push_back(i);
            continue;
        }
        if (occ[p][occ[p].size() -1] == p){
            occ[p].push_back(i);
        }
        else{
            ll pos = occ[p][occ[p].size() - 1];
            pairs[pos] = i;
            pairs[i] = pos;
            occ[p].pop_back();
        }
    }

    vl tree (4*n + 4, 0);
    ll s = 1;
    while (s < n){
        s *= 2;
    }
    s--;
    build(0, s, 1, tree);

    ll suma = 0;
    for (ll i = 0; i < n; i++){
        ll j = pairs[i];
        if (j-1 > i){
            suma += query(0, s, i+1, j-1, 1, tree);
            if (nums[i] < 0){
                suma++;
            }
        }
        update(0,s,j,1, tree);
    }
    return suma;
}

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

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