Submission #1312636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312636		coderg	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	42 ms	15260 KiB

shoes

#include "bits/stdc++.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FR(i,l,r) for(int i=(l);i>=(r);--i)
typedef long long ll;

const int maxn=1000005;
const int mod=1e9+7;
const int mox=2000*500+505;
const int inf=1e9;

ll count_swaps(vector<int> S){
    int n=S.size()/2;
    vector<vector<int> > pos(2*n+1);
    F(i,0,2*n){
        int s=abs(S[i]);
        if(S[i]<0)pos[s].pb(i);
        else pos[n+s].pb(i);
    }
    vector<int> curptr(2*n+1,0),T(2*n);
    vector<bool> vis(2*n,0);
    int curidx=0;
    F(i,0,2*n){
        if(vis[i])continue;
        int s=abs(S[i]),type=(S[i]<0)?0:1;
        int grpidx=s+(type==0?0:n);
        int pgrpidx=s+(type==0?n:0);
        vis[i]=1;
        curptr[grpidx]++;
        int val1=curptr[pgrpidx],val2=pos[pgrpidx][val1];
        vis[val2]=1;
        curptr[pgrpidx]++;
        if(type==0){
            T[i]=2*curidx;
            T[val2]=2*curidx+1;
        }else{
            T[i]=2*curidx+1;
            T[val2]=2*curidx;
        }
        curidx++;
    }
    ll inv=0;
    vector<int> bit(2*n+1,0);
    FR(i,2*n-1,0){
        int val=T[i];
        int sum=0,idx=val;
        while(idx){
            sum+=bit[idx];
            idx-=idx&-idx;
        }
        inv+=sum;
        idx=val+1;
        while(idx<=2*n){
            bit[idx]++;
            idx+=idx&-idx;
        }
    }
    return inv;
}

Compilation message (stderr)

shoes.cpp: In function 'void setIO(std::string)':
shoes.cpp:10:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
shoes.cpp:10:98: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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