Submission #832694

#	Time	Username	Problem	Language	Result	Execution time	Memory
832694		HorizonWest	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	212 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++) 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 = St.query(0, x), y1 = St.query(0, y);
		St.update(x, 1); St.update(y, -1);

		if(x > y)
			ans += (x - y);
		else
			ans += (y - (x + 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:65:7: warning: unused variable 'x1' [-Wunused-variable]
   65 |   int x1 = St.query(0, x), y1 = St.query(0, y);
      |       ^~
shoes.cpp:65:28: warning: unused variable 'y1' [-Wunused-variable]
   65 |   int x1 = St.query(0, x), y1 = St.query(0, y);
      |                            ^~

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