Submission #832755

#	Time	Username	Problem	Language	Result	Execution time	Memory
832755		HorizonWest	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	121 ms	138884 KiB

shoes

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

#define endl '\n'
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define all(x) x.begin(), x.end()
#define Mod long(1e9 + 7)

const int Max = 1e6 + 7, Inf = 1e9 + 7;

struct ABI
{
	vector <int> s;

	void update(int x, int k)
	{
		for(x; x < (int) s.size(); x += (x & -x))
			s[x] += k;
	}

	int sum(int x)
	{
		int ans = 0;
		for(x; x > 0; x -= (x & -x))
			ans += s[x];
		return ans;
	}

	int query(int l, int r)
	{
		if(l == 0) return sum(r);
		return sum(r) - sum(l-1);
	}

	ABI(int n)
	{
		s.assign(n+1, 0);
	}
};


long long count_swaps(std::vector<int> s)
{
	int n = (int) s.size(), ans = 0;

	vector <deque<int>> v(n+7, deque <int> ());

	for(int i = 0; i < n; i++)
		v[abs(s[i]) + (s[i] > 0 ? n/2+1 : 0)].push_back(i);

	vector <int> pass(n+7, 0); ABI St(n+7);

	for(int i = 0; i < n; i++)
    {
        if(!pass[i])
        {
            int x = v[abs(s[i])].front(), y = v[abs(s[i]) + n/2+1].front();
            v[abs(s[i])].pop_front();
            v[abs(s[i]) + n/2+1].pop_front();

            pass[x] = pass[y] = 1;

            int x1 = x + St.query(0, x+1), y1 = y + St.query(0, y+1);

            if(x > y) { St.update(x+1, -1); St.update(y+1, +1); }
            else { St.update(x+1, +1); St.update(y+1, -1); }

            if(x1 > y1)
                ans += (x1 - y1);
            else
                ans += (y1 - (x1 + 1));
        }
    }

	return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void ABI::update(int, int)':
shoes.cpp:20:7: warning: statement has no effect [-Wunused-value]
   20 |   for(x; x < (int) s.size(); x += (x & -x))
      |       ^
shoes.cpp: In member function 'int ABI::sum(int)':
shoes.cpp:27:7: warning: statement has no effect [-Wunused-value]
   27 |   for(x; x > 0; x -= (x & -x))
      |       ^

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