Submission #841725

#	Time	Username	Problem	Language	Result	Execution time	Memory
841725		Cookie	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	358 ms	149820 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#include<fstream>

using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 2e5 + 5;
using namespace std;
map<int, queue<int>>mp;
int bit[mxn + 1], to[mxn + 1], to2[mxn + 1];
bool vis[mxn + 1];
int n;
void upd(int p, int v){
    p++;
    while(p <= n){
        bit[p] += v; p += p & (-p);
    }
}
ll get(int p){
    p++;
    ll ans = 0;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
ll count_swaps(vt<int>s){


    n = sz(s);
    for(int i = 0; i < sz(s); i++){
        if(s[i] < 0){
            if(mp[-s[i]].size()){
                int id = mp[-s[i]].front(); mp[-s[i]].pop();
                to[i] = id; to2[id] = i;
            }else{
                mp[s[i]].push(i);
            }

        }else{
            if(mp[-s[i]].size()){
                int id = mp[-s[i]].front();
                mp[-s[i]].pop();
                to[id] = i; to2[i] = id;
            }else{
                mp[s[i]].push(i);
            }

        }

    }
    ll ans =0 ;
    for(int i = 0; i < n; i++)upd(i, 1);
    for(int i = 0; i < sz(s); i++){
        if(!vis[i]){
            if(s[i] > 0){
                ans += get(to2[i] -1); upd(to2[i], -1);
                ans += get(i - 1); upd(i, -1);
                vis[to2[i]] = 1;
            }else{
                ans += get(i - 1); upd(i, -1);
                ans += get(to[i] -1); upd(to[i], -1);
                vis[to[i]] = 1;
            }
        }
    }
    return(ans);

}
/*
int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}

*/

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