Submission #153354

#	Time	Username	Problem	Language	Result	Execution time	Memory
153354		Dilshod_Imomov	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	34 ms	3192 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;
    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 ( 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]) ) {
                    int val = S[j];
                    S.erase( S.begin() + j );
                    cnt += j - i;
                    vector < int > left(S.begin(), S.begin() + i);
                    vector < int > right( S.begin() + i, S.end() );
                    left.pb(val);
                    left.insert(left.end(), right.begin(), right.end());
                    S = left;
                    if ( S[i] > 0 ) {
                        swap( S[i], S[i + 1] );
                        cnt++;
                    }
                    break;
                }
            }
            i++;
        }
    }
    return cnt;
}
/*
int main() {
    /// Author: _Dilshod_
    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