Submission #570836

#	Time	Username	Problem	Language	Result	Execution time	Memory
570836		nohaxjustsoflo	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	571 ms	31808 KiB

shoes

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen(-1e9, 1e8); ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 1e6+50000;
const int mod = 998244353;
const int mxlogN = 34;
const int mxK = 26;
const int inf = 1e9;
const int K = 100000;
int cnt[mxN];
ll count_swaps(vector<int> s)
{
    map<int, vector<int>> mp;
    int n=s.size();
    ll ans=0;
    order_set os;
    for(int i=0; i<n; i++) mp[s[i]].push_back(i);
    for(int i=0; i<n; i++)
    {
        int x=abs(s[i]);
        int c=cnt[x];
        if(c==mp[x].size()) continue;
        //cout << "dodje\n";
        if(mp[x][c]>mp[-x][c])
        {
            ans+=mp[x][c]-mp[-x][c]-1;
            ans-=os.order_of_key(mp[x][c])-os.order_of_key(mp[-x][c]);
            os.insert(mp[x][c]);
        }
        else
        {
            ans+=mp[-x][c]-mp[x][c];
            ans-=os.order_of_key(mp[-x][c])-os.order_of_key(mp[x][c]);
            os.insert(mp[-x][c]);
        }
        cnt[x]++;
    }
    return ans;
}
/*
int main() {
	int n; cin >> n;
	vector<int> s(n);
	for(int i=0; i<n; i++) cin >> s[i];
	cout << count_swaps(s);
	return 0;
}*/

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:32:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if(c==mp[x].size()) continue;
      |            ~^~~~~~~~~~~~~~

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