Submission #832718

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

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

        if(!pass[j])
        {
            int x = v[abs(s[j])].back(), y = v[abs(s[j]) + n/2].back();
            v[abs(s[j])].pop_back();
            v[abs(s[j]) + n/2].pop_back();

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

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

	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))
      |       ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:68:17: warning: unused variable 'x1' [-Wunused-variable]
   68 |             int x1 = St.query(0, x+1), y1 = St.query(0, y+1);
      |                 ^~
shoes.cpp:68:40: warning: unused variable 'y1' [-Wunused-variable]
   68 |             int x1 = St.query(0, x+1), y1 = St.query(0, y+1);
      |                                        ^~
shoes.cpp:90:17: warning: unused variable 'x1' [-Wunused-variable]
   90 |             int x1 = St.query(0, x+1), y1 = St.query(0, y+1);
      |                 ^~
shoes.cpp:90:40: warning: unused variable 'y1' [-Wunused-variable]
   90 |             int x1 = St.query(0, x+1), y1 = St.query(0, y+1);
      |                                        ^~

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