Submission #422653

#	Time	Username	Problem	Language	Result	Execution time	Memory
422653		oleh1421	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	150 ms	32924 KiB

shoes

//#include "grader.cpp"
#include "shoes.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=200010;
int t[N];
void upd(int n,int pos,int x){
    for (;pos<=n;pos|=pos+1) t[pos]+=x;
}
int get(int pos){
    int sum=0;
    for (;pos>=0;pos&=pos+1,pos--) sum+=t[pos];
    return sum;
}
set<int>open[N],close[N];
int r[N];
ll count_swaps(vector<int> s) {
    for (int i=0;i<s.size();i++) s[i]=-s[i];
    for (int i=0;i<s.size();i++){
        if (s[i]>0) open[s[i]].insert(i);
        else if (s[i]<0) close[-s[i]].insert(i);
    }
    ll res=0ll;
    for (int i=0;i<s.size();i++){
        if (r[i]==-1) continue;

        if (s[i]>0){
            r[i]=(*close[s[i]].begin());
            r[r[i]]=-1;
            close[s[i]].erase(close[s[i]].begin());
            open[s[i]].erase(i);
        } else {
            r[i]=(*open[-s[i]].begin());
            r[r[i]]=-1;
            open[-s[i]].erase(open[-s[i]].begin());
            res++;
            close[-s[i]].erase(i);
        }
//        cout<<i<<" "<<r[i]<<endl;
    }
    for (int i=0;i<s.size();i++){
        upd(s.size(),i,1);
    }
    for (int i=0;i<s.size();i++){
        if (r[i]==-1) continue;
//        cout<<i<<" "<<r[i]<<endl;
        res+=get(r[i]-1)-get(i);
        upd(s.size(),r[i],-1);
    }
	return res;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i=0;i<s.size();i++) s[i]=-s[i];
      |                  ~^~~~~~~~~
shoes.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i=0;i<s.size();i++){
      |                  ~^~~~~~~~~
shoes.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i=0;i<s.size();i++){
      |                  ~^~~~~~~~~
shoes.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0;i<s.size();i++){
      |                  ~^~~~~~~~~
shoes.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     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