Submission #1069171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069171		hasan2006	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	190 ms	282744 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 2e5 + 9 , mod = 1e9 + 7;
ll a[N] ,  b[N] , dp[N];
vector<int>v[N];

void add(int x , int y){
    while(x <= 200000){
        dp[x] += y;
        x += x & (-x);
    }
}

ll get(int x){
    ll ans = 0;
    while(x > 0)
        ans += dp[x] , x -= (x & (-x));
    return ans;
}
deque<int>d[N][2];

//int press(string a){}
ll count_swaps(vector<int>vc){
    ll i , j , l , r , s  = 0, f , n , m , x , y , k;
    n = vc.size();
    for(i = 1; i <= n; i++){
        a[i] = vc[i - 1];
        b[i] = abs(a[i]);
        add(i , 1);
        d[b[i]][(a[i] > 0)].pb(i);
    }
    for(i = 1; i <= n; i++){
        if(d[b[i]][(a[i] > 0)].size() && d[b[i]][(a[i] > 0)].front() == i){
            x = d[b[i]][1 - (a[i] > 0)].front();
            add(i , -1);
            d[b[i]][(a[i] > 0)].pop_front();
            d[b[i]][1 - (a[i] > 0)].pop_front();
            add(x , -1);
            s += get(x) + (a[i] > 0);
        }
    }
    return s;
}

/*
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    cout<<count_swaps({2, 1, -1, -2});
}*/
// Author : حسن

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:43:12: warning: unused variable 'j' [-Wunused-variable]
   43 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |            ^
shoes.cpp:43:16: warning: unused variable 'l' [-Wunused-variable]
   43 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                ^
shoes.cpp:43:20: warning: unused variable 'r' [-Wunused-variable]
   43 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                    ^
shoes.cpp:43:32: warning: unused variable 'f' [-Wunused-variable]
   43 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                ^
shoes.cpp:43:40: warning: unused variable 'm' [-Wunused-variable]
   43 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                        ^
shoes.cpp:43:48: warning: unused variable 'y' [-Wunused-variable]
   43 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                                ^
shoes.cpp:43:52: warning: unused variable 'k' [-Wunused-variable]
   43 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                                    ^

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