제출 #228681

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

shoes

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include "shoes.h"


using namespace std;

typedef long long ll;

vector<ll> t(4*100001, 0);

ll getSum(ll idx){
    ll sum = 0;
    idx++;
    while(idx > 0){
        sum += t[idx];
        idx -= idx & (-idx);
    }
    return sum;
}

void updateF(ll n, ll idx, ll val){
    idx++;
    while(idx <= n){
        t[idx] += val;
        idx += idx & (-idx);
    }
}

void build(vector<ll> arr, ll n){
    for (ll i = 1; i <= n; i++)
        t[i] = 0;
    for (ll i = 0; i < n; i++)
        updateF(n, i, arr[i]);
}

ll count_swaps(vector<ll> s){
    ll n = s.size()/2;
    
    vector<ll> arr(2*n, 0);
    build(arr, 2*n);
    
    vector<queue<ll>> cnt(2*n, queue<ll> ());
    queue<ll> q;
    vector<bool> koristen(2*n, false);
    for (ll i = 2*n - 1; i >= 0; i--){
        if (!koristen[abs(s[i])]){
            q.push(i);
            koristen[abs(s[i])] = true;
        }
        else{
            cnt[abs(s[i])].push((i + 1)*abs(s[i])/s[i]);
            koristen[abs(s[i])] = false;
        }
    }
    
    ll res = 0;
    ll pocetak = 2*n - 2;
    
    while(!q.empty()){
        ll curr = q.front();
        ll par =  cnt[abs(s[curr])].front();
        q.pop(); cnt[abs(s[curr])].pop();
        if (par > 0)
            res++;
        else
            par = -par;
        par--;
        par += getSum(par);
        res += pocetak - par;
        updateF(2*n, par, -1);
        pocetak -= 2;
    }
    
    return res;
}

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

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