Submission #412144

#	Time	Username	Problem	Language	Result	Execution time	Memory
412144		dolijan	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	237 ms	141632 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long cnt=0;
const int mn=1e5+100;
vector<queue<int> > poz(mn);
vector<queue<int> > neg(mn);
set<int> skup;
int st[8*mn];
void update(int l,int r,int poz,int tren)
{
    if(l==r)
    {
        st[tren]++;
        return;
    }
    int mid=(l+r)/2;
    if(poz<=mid) update(l,mid,poz,2*tren+1);
    else update(mid+1,r,poz,2*tren+2);
    st[tren]=st[2*tren+1]+st[2*tren+2];
}
int query(int l,int r,int L,int R,int node)
{
    if(R<l || r<L) return 0;
    if(l<=L && R<=r) return st[node];
    int mid=(L+R)/2;
    return query(l,r,L,mid,2*node+1)+query(l,r,mid+1,R,2*node+2);
}
void resi(int l,int r,int n,std::vector<int> s)
{
    for(l;l<=r;l++)
    {
    if(l>=r) continue;
    int prva=s[l];
    if(query(l,l,0,n-1,0)==1) continue;
    if(prva>0)
    {
        poz[prva].pop();
        int i=neg[prva].front();
        neg[prva].pop();
        //cout<<"Obradjujemo pozitivan "<<prva<<endl;
        //cout<<i<<endl;
        int manji=query(l+1,i,0,n-1,0);
        //cout<<"Kveri uradio "<<manji<<endl;
        cnt+=(i-l-manji);
        //cout<<cnt<<endl;
        update(0,n-1,i,0);
        //for(int i=0;i<n;i++) cout<<st[i]<<" ";
        //cout<<endl;
    }
    else
    {
        prva*=-1;
        neg[prva].pop();
        int i=poz[prva].front();
        //cout<<"Obradjujemo negativan "<<prva<<endl;
        //cout<<i<<endl;
        poz[prva].pop();
        int manji=query(l+1,i,0,n-1,0);
        //cout<<"Uradio kveri ide gas "<<manji<<endl;
        cnt+=(i-(l+1)-manji);
        //cout<<cnt<<endl;
        update(0,n-1,i,0);
    }
    }
}
long long count_swaps(std::vector<int> s) {
    int n=s.size();
    int l=0;
    int r=n-1;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]>0) poz[s[i]].push(i);
        else neg[-s[i]].push(i);
    }
    resi(l,r,n,s);
	return cnt;
}

Compilation message (stderr)

shoes.cpp: In function 'void resi(int, int, int, std::vector<int>)':
shoes.cpp:31:9: warning: statement has no effect [-Wunused-value]
   31 |     for(l;l<=r;l++)
      |         ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~

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