Submission #153391

#	Time	Username	Problem	Language	Result	Execution time	Memory
153391		Dilshod_Imomov	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	32 ms	3196 KiB

shoes

# include <bits/stdc++.h>
# pragma GCC optimize("Ofast")
# define file
# define ll long long
# define fi first
# define se second
# define pb push_back
# define pf push_front
# define For(i, a, b) for( ll i = a; i < b; i++ )
# define in insert
# define all(a) a.begin(),a.end()
# define pi pair < ll, ll >
# define readfile(file) freopen ( (file + ".in").c_str(), "r", stdin)
# define writefile(file) freopen ( (file + ".out").c_str(), "w", stdout)
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
# define SET(file) readfile(file);writefile(file);
# define LARGE 100005
using namespace std;

ll count_swaps( vector < int > S ) {
    ll cnt = 0;
    int n = S.size();
    ll c = 0;
    ll x = 0;
    For ( i, 0, n / 2 ) {
        if ( S[i] < 0 && S[i] != S[i + n / 2] && abs(S[i]) == abs(S[i + n / 2]) ) {
            c++;
        }
        if ( abs( S[i] ) == abs( S[i + n / 2] ) ) {
            x++;
        }
    }
    if ( c == n / 2 ) {
        ll ans = n / 2 - 1;
        ans *= n / 2;
        ans /= 2;
        return ans;
    }
    if ( x == n / 2 ) {
        vector < int > ms, ps;
        For ( i, 0, n ) {
            if ( S[i] > 0 ) ps.pb(i);
            else ms.pb(i);
        }
        For ( i, 0, n ) {
            if ( i > ms[0] ) ms.erase(ms.begin());
            if ( i > ps[0] ) ps.erase(ps.begin());
            if ( S[i] != S[i + 1] && abs(S[i]) == abs(S[i]) && S[i] < 0 ) {
                i++;
            }
            else {
                if ( S[i] < 0 ) {
                    for ( int j = ps[0]; j > i + 1; j-- ) {
                        swap( S[j], S[j - 1] );
                        cnt++;
                    }
                }
                else {
                    for ( int j = ms[0]; j > i; j-- ) {
                        swap(S[j], S[j - 1]);
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
    For ( i, 0, n ) {
        if ( S[i] != S[i + 1] && abs(S[i]) == abs(S[i + 1]) && S[i] < 0 ) {
            i++;
        }
        else {
            For ( j, i + 1, n ) {
                if ( S[i] != S[j] && abs(S[i]) == abs(S[j]) ) {
                    for ( int k = j; k > i + 1; k-- ) {
                        swap( S[k], S[k - 1] );
                        cnt++;
                    }
                    if ( S[i] > 0 ) {
                        swap( S[i], S[i + 1] );
                        cnt++;
                    }
                    break;
                }
            }
            i++;
        }
    }
    return cnt;
}
/*
int main() {
    /// Author: _Dilshod_
    #ifdef file
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif // file
    speed;
    vector < int > S = {-2, 2, 2, -2, -2, 2};
    cout << count_swaps(S);
}
*/

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