Submission #1287348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287348		anfi	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	51 ms	5988 KiB

shoes

#include"shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = (1ll << 60);
const int mod = 998244353;
#define fi first
#define se second

int binpow(int a, int b){
    int ans = 1;
    while(b){
        if(b&1) ans = a*ans%mod;
        a = a*a%mod;
        b >>=1;
    }
    return ans;
}
int N;
struct fenwick{
    int n;
    vector<int> bit;
    fenwick(int n) : n(n), bit(2*n+5, 0){}
    void update(int idx){
        for(int i = idx;i <= 2*n; i += i&-i) bit[i]+= 1;
    }
    int query(int idx){
        int ans = 0;
        for(int i = idx; i > 0; i -= i&-i) ans += bit[i];
        return ans;
    }

    void ins(int x,ll &kom){
        update(x);
        kom += x-query(x);
    }
};

ll count_swaps(vector<int> s){
    N = s.size()/2;
    ll kom = 0;
    vector<pair<int,int>> l,r,p(N);
    for(int i = 0; i < 2*N; i++){
        if(s[i] > 0){
            r.push_back({s[i], i+1});
        }else{
            l.push_back({-s[i], i+1});
        }
    }
    sort(l.begin(), l.end());
    sort(r.begin(), r.end());
    for(int i = 0; i < N; i++){
        p[i].fi = l[i].se;
        p[i].se = r[i].se;
        if(p[i].fi > p[i].se){
            swap(p[i].fi, p[i].se);
            kom++;
        }
    }
    fenwick fk(2*N);
    sort(p.begin(),p.end());
    for(int i = 0; i < N; i++){
        fk.ins(p[i].fi, kom);
        fk.ins(p[i].se, kom);
    }
    return kom;
}

Compilation message (stderr)

shoes.cpp:5:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
    5 | const int inf = (1ll << 60);
      |                 ~~~~~^~~~~~

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