Submission #169895

#	Time	Username	Problem	Language	Result	Execution time	Memory
169895		whttt	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KiB

shoes

#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

ll count_swaps(vector<ll> S){
    ll n = S.size()/2;
    if(n == 1){
        if(S[0] < 0){
            return 0;
        } else {
            return 1;
        }
    }
    vector<vector<ll>> vyskytR;
    vector<vector<ll>> vyskytL;
    for(ll i = 0;i <= n;i++){
        vyskytL.push_back({});
        vyskytR.push_back({});
    }
    ll sol = 0;
    ll sqrtt = 1;
    while(sqrtt * sqrtt < 2*n){
        sqrtt++;
    }
    ll sqrtDec[n/sqrtt];
    ll sum[n];
    for(ll i = 0;i < 2*n/sqrtt;i++){
        sqrtDec[i] = 0;
    }
    for(ll i = 0;i < 2*n;i++){
        sum[i] = 0;
    }
    for(ll i = 0;i < 2*n;i++){
        if(S[i] < 0){
            vyskytL[-S[i]].push_back(i);
        } else {
            vyskytR[S[i]].push_back(i);
        }
    }
    for(ll i = 0;i < n;i++){
        reverse(vyskytR[i].begin(),vyskytR[i].end());
        reverse(vyskytL[i].begin(),vyskytL[i].end());
    }
    ll where = 0;
    ll where2 = 0;
    ll countt = 0;
    ll start;
    while(1){
        if(where >= n){
            break;
        }
        if(sum[where]==1){
            where++;
            continue;
        }
        if(S[where] < 0){
            where2 = vyskytR[-S[where]][vyskytR[-S[where]].size()-1];
            // countt sa nastavi na pocet pouzitych medzi where a where2
            countt = 0;
            start = where;
            while(1){
                if(start > where2){
                    break;
                }
                if(start % sqrtt == 0 && start+sqrtt-1 <= where2){
                    countt += sqrtDec[start/sqrtt];
                    start += sqrtt;
                } else {
                    countt += sum[start];
                    start++;
                }
            }
            sol += where2-where-1-countt;
            vyskytR[-S[where]].pop_back();
            sum[where2] = 1;
            sqrtDec[where2/sqrtt]++;
            where++;
            vyskytL[-S[where-1]].pop_back();
            //cout << -S[where-1] << "???" << endl;
        } else {
            where2 = vyskytL[S[where]][vyskytL[S[where]].size()-1];
            // countt sa nastavi na pocet pouzitych medzi where a where2
            countt = 0;
            start = where;
            while(1){
                if(start > where2){
                    break;
                }
                if(start % sqrtt == 0 && start+sqrtt-1 <= where2){
                    countt += sqrtDec[start/sqrtt];
                    start += sqrtt;
                } else {
                    countt += sum[start];
                    start++;
                }
            }
            sol += where2-where-countt;
            vyskytL[S[where]].pop_back();
            sum[where2] = 1;
            sqrtDec[where2/sqrtt]++;
            where++;
            vyskytR[S[where-1]].pop_back();
        }
        //cout << countt << endl;
        //cout << where-1 << " " << where2 << endl;
        //cout << sol << endl;
        //cout << "----" << endl;
    }
    return sol;
}

/*
int main(int argc, const char * argv[]) {
    
    
    
    cout << count_swaps({2,1,-1,-2}) << endl;
    cout << count_swaps({-2,2,2,-2,-2,2}) << endl;
    cout << count_swaps({-1,1}) << endl;
    cout << count_swaps({2,-2}) << endl;
    cout << count_swaps({-3,2,1,-4,2,-2,3,4,-1,-2}) << endl;
    
    
    return 0;
}
*/

Compilation message (stderr)

/tmp/ccl9yfzC.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