Submission #832752

#	Time	Username	Problem	Language	Result	Execution time	Memory
832752		HorizonWest	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	116 ms	138824 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)
	{
	    x = max(1, x);
		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+1, deque <int> ());

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

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

	for(int i = 0; i < n; i++)
    {
        int j = n - i - 1;

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

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

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

            if(x > y) { St.update(x, -1); St.update(y, +1); }
            else { St.update(x, +1); St.update(y, -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:21:7: warning: statement has no effect [-Wunused-value]
   21 |   for(x; x < (int) s.size(); x += (x & -x))
      |       ^
shoes.cpp: In member function 'int ABI::sum(int)':
shoes.cpp:28:7: warning: statement has no effect [-Wunused-value]
   28 |   for(x; x > 0; x -= (x & -x))
      |       ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:59:13: warning: unused variable 'j' [-Wunused-variable]
   59 |         int j = n - i - 1;
      |             ^

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