Submission #285496

#	Time	Username	Problem	Language	Result	Execution time	Memory
285496		MKopchev	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	445 ms	26136 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=2e5+42;

int fenwick[nmax];
void update(int pos)
{
    while(pos<nmax)
    {
        fenwick[pos]++;
        pos=pos+(pos&(-pos));
    }
}
int query(int pos)
{
    //cout<<"query "<<pos<<endl;

    int ret=0;
    while(pos)
    {
        ret=ret+fenwick[pos];
        pos=pos-(pos&(-pos));
    }
    return ret;
}

int sum(int le,int ri)
{
    return query(ri)-query(le-1);
}

map<int, vector<int> > seen;

bool paired[nmax];

long long outp;

void my_match(int i,int j)
{
    i++;
    j++;

    //cout<<"my_match "<<i<<" "<<j<<endl;

    int mem_i=i,mem_j=j;

    i=i+sum(i,nmax-1);
    j=j+sum(j,nmax-1);

    outp+=j-i-1;

    //cout<<"i= "<<i<<" j= "<<j<<endl;

    update(mem_i);
    update(mem_j);

    paired[mem_i]=1;
    paired[mem_j]=1;
}
long long count_swaps(std::vector<int> s)
{
    for(int i=s.size()-1;i>=0;i--)
        seen[s[i]].push_back(i);

	for(int i=0;i<s.size();i++)
        if(paired[i+1]==0)
        {
            if(s[i]>0)outp++;

            my_match(seen[s[i]].back(),seen[-s[i]].back());

            seen[s[i]].pop_back();
            seen[-s[i]].pop_back();
        }
    return outp;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:64:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |     for(int i=s.size()-1;i>=0;i--)
      |     ^~~
shoes.cpp:67:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   67 |  for(int i=0;i<s.size();i++)
      |  ^~~
shoes.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  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