Submission #153360

#	Time	Username	Problem	Language	Result	Execution time	Memory
153360		Dilshod_Imomov	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1081 ms	3028 KiB

shoes

# include <bits/stdc++.h>
# pragma GCC optimize("Ofast")
# 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 ( x == n / 2 ) {
        vector < int > ms;
        vector < int > ps;
        For ( i, 0, n ) {
            if ( S[i] < 0 ) ms.pb(i);
            else ps.pb(i);
        }
        For ( i, 0, n ) {
            if ( S[i] != S[i + 1] && abs(S[i]) == abs(S[i + 1]) && S[i] < 0 ) {
                i++;
            }
            else {
                if ( S[i] > 0 ) {
                    for ( int j = ms[0]; j > i; j-- ) {
                        swap( S[j], S[j - 1] );
                        cnt++;
                    }
                    ms.erase(ms.begin());
                }
                else {
                    for ( int j = ps[0]; j > i + 1; j-- ) {
                        swap( S[j], S[j - 1] );
                        cnt++;
                    }
                    ps.erase(ps.begin());
                }
                i++;
            }
        }
        return cnt;
    }
    if ( c == n / 2 ) {
        ll ans = n / 2 - 1;
        ans *= n / 2;
        ans /= 2;
        return ans;
    }
    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, 2 * 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_
    speed;
    vector < int > S = {1, 1, 1, -1, -1, -1};
    cout << count_swaps(S);
}
*/

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