Submission #153393

#	Time	Username	Problem	Language	Result	Execution time	Memory
153393		Dilshod_Imomov	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	1079 ms	2844 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;
        int sz1 = 0, sz2 = 0;
        For ( i, 0, n ) {
            if ( S[i] > 0 ) {
                ps.pb(i);
                sz1++;
            }
            else {
                ms.pb(i);
                sz2++;
            }
        }
        For ( i, 0, n ) {
            if ( sz2 && i >= ms[0] ) {
                ms.erase(ms.begin());
                sz2--;
            }
            if ( sz1 && i >= ps[0] ) {
                ps.erase(ps.begin());
                sz1--;
            }
            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++;
                    }
                    ps.erase(ps.begin());
                    sz1--;
                }
                else {
                    for ( int j = ms[0]; j > i; j-- ) {
                        swap(S[j], S[j - 1]);
                        cnt++;
                    }
                    ms.erase(ms.begin());
                    sz2--;
                }
                i++;
            }
        }
        return cnt;
    }
    For ( i, 0, n - 1 ) {
        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, 1, -1, -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