Submission #984530

#	Time	Username	Problem	Language	Result	Execution time	Memory
984530		SzymonKrzywda	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1095 ms	2008 KiB

shoes

//#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

const int base = 2<<18;
int tree[base*2+7];

void edit(int n){
    n+=base;
    while (n>0){
        tree[n] += 1;
        n/=2;
    }
}

int query(int a,int b){
    a+=base-1;
    b+=base+1;
    int wynik=0;
    while (a/2 != b/2){
        if (a%2==0) wynik += tree[a+1];
        if (b%2==1) wynik += tree[b-1];
        a/=2;
        b/=2;
    }
    return wynik;
}


long unsigned int count_swaps(vector<int>S){
    long long wynik = 0,len=S.size(),idx_1,akt_liczba,idx_2;
    for (long unsigned int i=0; i<len; i+=2){
        /*
        for (long unsigned int j=i; j<len; j++){
            if (S[j]<0){
                idx_1 = j;
                akt_liczba = -S[j];
                break;
            }
            
        }
        */
        idx_1 = i;
        akt_liczba = -S[i];
        /*for (int j=idx_1; j>i; j--){
            swap(S[j],S[j-1]);
            wynik+=1;
        }*/
        
        for (long unsigned int j=i; j<len; j++){
            if (S[j]==akt_liczba){
                idx_2 = j;
                break;
            }
        }
        if (akt_liczba<0) idx_1 = i;
        else idx_1=i+1;
        //cout << idx_1 << " " << akt_liczba << endl;
        for (int j=idx_2; j>idx_1; j--){
            swap(S[j],S[j-1]);
            wynik +=1;
        }
    }
    //cout << S[0] << " " << S[1] << " " << S[2] << " " << endl;
    return wynik;
}

Compilation message (stderr)

shoes.cpp: In function 'long unsigned int count_swaps(std::vector<int>)':
shoes.cpp:32:34: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'long long int' [-Wsign-compare]
   32 |     for (long unsigned int i=0; i<len; i+=2){
      |                                 ~^~~~
shoes.cpp:50:38: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'long long int' [-Wsign-compare]
   50 |         for (long unsigned int j=i; j<len; j++){
      |                                     ~^~~~
shoes.cpp:59:18: warning: 'idx_2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |         for (int j=idx_2; j>idx_1; j--){
      |                  ^

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