Submission #1072049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072049		PikachudoraEHE	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	132 ms	141672 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+5;
const int OFFSET = 1e5;
int n;
int a[N],chk[N];
queue<int>q[N];
struct fenwick{
   int f[N];
   void update(int idx,int v){
    for(int i=idx;i<N;i+=i&-i){
            f[i]+=v;
    }
    return;
   }
   int sum(int idx){
    int s=0;
    for(int i=idx;i>0;i-=i&-i){
        s+=f[i];
    }
    return s;
   }
}f,f2;
long long count_swaps(std::vector<int> s){
    for(int i=1;i<=s.size();i++){a[i]=s[i-1];f.update(i,1);}
    ll ans=0;ll n = s.size();
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            q[OFFSET-a[i]].push(i);
        }
        else{
            q[a[i]].push(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(chk[i])continue;int ii;
        if(a[i]<0){
            ii = q[(-1)*a[i]].front();
            q[(-1)*a[i]].pop();
            q[OFFSET-a[i]].pop();
            chk[ii]=1;
            ans+=f.sum(ii)-f.sum(i)-1;
        }
        else{
            ii = q[OFFSET+a[i]].front();
            q[OFFSET+a[i]].pop();
            q[a[i]].pop();
            chk[ii]=1;
            ans+=f.sum(ii)-f.sum(i);
        }
        f.update(ii,-1);f.update(i,-1);
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=1;i<=s.size();i++){a[i]=s[i-1];f.update(i,1);}
      |                 ~^~~~~~~~~~
shoes.cpp:38:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |         if(chk[i])continue;int ii;
      |         ^~
shoes.cpp:38:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |         if(chk[i])continue;int ii;
      |                            ^~~

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