Submission #825352

#	Time	Username	Problem	Language	Result	Execution time	Memory
825352		tomruk	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	324 ms	44616 KiB

shoes

    #include "shoes.h"
    #include <bits/stdc++.h>
    #define N 200005
    using namespace std;
    struct BIT{
    	vector<int> bit;
    	int n;
    	BIT(int size){
    		n = size;
    		bit.assign(n,0);
    	}
    	void upd(int pos,int val){
    		for(++pos;pos<n;pos += pos & -pos){
    			bit[pos] += val;
    		}
    	}
    	int get(int pos){
    		int ret = 0;
    		for(++pos;pos > 0;pos -= pos & -pos){
    			ret += bit[pos];
    		}
    		return ret;
    	}
    	int get(int l,int r){
    		return get(r) - get(l-1);
    	}
    };
    vector<int> l[N];
    vector<int> r[N];
    long long solve(vector<int> a,vector<int> b){
    	long long ret = 0;
    	BIT bt(N);
    	map<int,vector<int>> mp;
    	int sz = a.size();
    	for(int i = sz-1;i>=0;i--){
    		mp[a[i]].push_back(i);
    	}
    	for(int i = 0;i<sz;i++){
    		int ps = mp[b[i]].back() + bt.get(mp[b[i]].back()+1,sz);
    		ret += ps - i;
    		bt.upd(mp[b[i]].back(),1);
    		mp[b[i]].pop_back();
    	}
    	return ret;
    }
    long long count_swaps(vector<int> s){
    	int n = s.size()/2;
    	int m = s.size();
    	for(int i = 0;i<m;i++){
    		if(s[i] < 0)l[-s[i]].push_back(i);
    		else r[s[i]].push_back(i);
    	}
    	vector<pair<int,int>> v;
    	for(int i = 1;i<=n;i++){
    		for(int j = 0;j<l[i].size();j++){
    			v.push_back({l[i][j] + r[i][j],i});
    		}
    	}
    	sort(v.begin(),v.end());
    	vector<int> t;
    	for(auto u:v){
    		t.push_back(-u.second);
    		t.push_back(u.second);
    	}
    	return solve(s,t);
    }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |       for(int j = 0;j<l[i].size();j++){
      |                     ~^~~~~~~~~~~~

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