oj.uz

Submission #143378

# Submission time Handle Problem Language Result Execution time Memory
143378 2019-08-13T21:53:58 Z abeker Arranging Shoes (IOI19_shoes) C++17
10 / 100
 18 ms 14456 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 5;

int N;
vector <int> lft[MAXN], rig[MAXN], perm[MAXN];
	
ll inversions(vector <int> v) {
	reverse(v.begin(), v.end());
	int len = v.size();
	vector <int> fen(len + 1, 0);
	ll res = 0;
	for (auto it : v) {
		for (int x = it; x; x -= x & -x)
			res += fen[x];
		for (int x = it + 1; x <= len; x += x & -x)
			fen[x]++;
	}
	return res;
}

ll count_swaps(vector <int> shoes) {
	N = shoes.size();
	for (int i = 0; i < N; i++) {
		int sz = abs(shoes[i]);
		if (shoes[i] < 0) {
			perm[sz].push_back(2 * lft[sz].size());					
			lft[sz].push_back(i);
		}
		else {
			perm[sz].push_back(2 * rig[sz].size() + 1);
			rig[sz].push_back(i);
		}
	}
	
	ll sol = 0;
	for (int i = 0; i < N; i++) {
		sol += inversions(perm[i]);
		for (int j = 0; j < lft[i].size(); j++)
			sol += abs(lft[i][j] - rig[i][j]) - 1;
	}
	
	return sol;
}

Compilation message

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lft[i].size(); j++)
                   ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14328 KB Output is correct
2 Correct 15 ms 14456 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14328 KB Output is correct
2 Correct 15 ms 14456 KB Output is correct
3 Correct 17 ms 14452 KB Output is correct
4 Correct 15 ms 14328 KB Output is correct
5 Correct 18 ms 14428 KB Output is correct
6 Correct 15 ms 14428 KB Output is correct
7 Incorrect 16 ms 14428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14328 KB Output is correct
2 Correct 15 ms 14456 KB Output is correct
3 Incorrect 15 ms 14356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14428 KB Output is correct
2 Incorrect 14 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14328 KB Output is correct
2 Correct 15 ms 14456 KB Output is correct
3 Correct 17 ms 14452 KB Output is correct
4 Correct 15 ms 14328 KB Output is correct
5 Correct 18 ms 14428 KB Output is correct
6 Correct 15 ms 14428 KB Output is correct
7 Incorrect 16 ms 14428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14328 KB Output is correct
2 Correct 15 ms 14456 KB Output is correct
3 Correct 17 ms 14452 KB Output is correct
4 Correct 15 ms 14328 KB Output is correct
5 Correct 18 ms 14428 KB Output is correct
6 Correct 15 ms 14428 KB Output is correct
7 Incorrect 16 ms 14428 KB Output isn't correct
8 Halted 0 ms 0 KB -