Submission #200390

#	Time	Username	Problem	Language	Result	Execution time	Memory
200390		Leonardo_Paes	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1088 ms	380 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

bool mark[maxn];

long long count_swaps(vector<int> s){
    int n = s.size();

    int ans = 0, cnt = 0;

    while(cnt != n/2){
        for(int i=0; i<n; i++){
            if(s[i] < 0 and !mark[s[i]]){
                if(i+1 < n and s[i+1] == -s[i]) mark[s[i]] = 1, cnt++;
                else{
                    int aux;
                    for(int j=0; j<n; j++){
                        if(s[j] == -s[i]) aux = j;
                    }

                    bool ok = false;

                    while(aux < i){
                        swap(s[aux], s[aux+1]);
                        aux++;
                        ans++;
                        ok = 1;
                    }

                    if(!ok){
                        while(aux > i){
                            if(aux == i+1) break;
                            swap(s[aux], s[aux-1]);
                            aux--;
                            ans++;
                        }
                    }

                    mark[s[i]] = 1;
                    cnt++;
                }
            }
        }
    }

    return ans;
}

/*int main(){
    int n;

    cin >> n;

    vector<int> s;

    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        s.push_back(x);
    }

    cout << count_swaps(s) << endl;
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:16:39: warning: array subscript is below array bounds [-Warray-bounds]
             if(s[i] < 0 and !mark[s[i]]){
                              ~~~~~~~~~^
shoes.cpp:17:58: warning: array subscript is below array bounds [-Warray-bounds]
                 if(i+1 < n and s[i+1] == -s[i]) mark[s[i]] = 1, cnt++;
                                                 ~~~~~~~~~^

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