| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 310821 | MilosMilutinovic | Arranging Shoes (IOI19_shoes) | C++14 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int N = 1e5 + 1;
vector<int> fenw(N, 0);
vector<vector<int>> left(N), right(N);
set<int> s;
void Add(int x, int val) {
for (; x < N; x += x & -x) {
fenw[x] += val;
}
}
long long Get(int x) {
long long res = 0;
for (; x > 0; x -= x & -x) {
res += fenw[x];
}
return res;
}
long long count_swaps(vector<int> a) {
int n = (int) a.size();
vector<int> b(n + 1);
for (int i = 0; i < n; i++) {
b[i + 1] = a[i];
if (b[i + 1] < 0) {
left[-b[i + 1]].push_back(i + 1);
} else {
right[b[i + 1]].push_back(i + 1);
}
s.insert(i + 1);
}
for (int i = 1; i <= n; i++) {
Add(i, 1);
}
long long ans = 0;
for (int i = 1; i <= n / 2; i++) {
int p = *s.begin();
if (b[p] > 0) {
ans += Get(N) - Get(left[b[p].back()]) - 1;
s.erase(p);
s.erase(left[b[p].back()]);
Add(p, -1);
Add(left[b[p].back()], -1);
right[b[p]].pop_back();
left[b[p]].pop_back();
} else {
ans += Get(N) - Get(right[-b[p].back()]) - 1;
s.erase(p);
s.erase(right[-b[p].back()]);
Add(p, -1);
Add(right[-b[p].back()], -1);
right[-b[p]].pop_back();
left[-b[p]].pop_back();
}
}
return ans;
}
/*int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << count_swaps(a) << '\n';
return 0;
}*/
Compilation message (stderr)
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:32:7: error: reference to 'left' is ambiguous
32 | left[-b[i + 1]].push_back(i + 1);
| ^~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1006:3: note: candidates are: 'std::ios_base& std::left(std::ios_base&)'
1006 | left(ios_base& __base)
| ^~~~
shoes.cpp:9:21: note: 'std::vector<std::vector<int> > left'
9 | vector<vector<int>> left(N), right(N);
| ^~~~
shoes.cpp:34:7: error: reference to 'right' is ambiguous
34 | right[b[i + 1]].push_back(i + 1);
| ^~~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1014:3: note: candidates are: 'std::ios_base& std::right(std::ios_base&)'
1014 | right(ios_base& __base)
| ^~~~~
shoes.cpp:9:30: note: 'std::vector<std::vector<int> > right'
9 | vector<vector<int>> left(N), right(N);
| ^~~~~
shoes.cpp:45:27: error: reference to 'left' is ambiguous
45 | ans += Get(N) - Get(left[b[p].back()]) - 1;
| ^~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1006:3: note: candidates are: 'std::ios_base& std::left(std::ios_base&)'
1006 | left(ios_base& __base)
| ^~~~
shoes.cpp:9:21: note: 'std::vector<std::vector<int> > left'
9 | vector<vector<int>> left(N), right(N);
| ^~~~
shoes.cpp:45:37: error: request for member 'back' in 'b.std::vector<int>::operator[](((std::vector<int>::size_type)p))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
45 | ans += Get(N) - Get(left[b[p].back()]) - 1;
| ^~~~
shoes.cpp:47:15: error: reference to 'left' is ambiguous
47 | s.erase(left[b[p].back()]);
| ^~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1006:3: note: candidates are: 'std::ios_base& std::left(std::ios_base&)'
1006 | left(ios_base& __base)
| ^~~~
shoes.cpp:9:21: note: 'std::vector<std::vector<int> > left'
9 | vector<vector<int>> left(N), right(N);
| ^~~~
shoes.cpp:47:25: error: request for member 'back' in 'b.std::vector<int>::operator[](((std::vector<int>::size_type)p))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
47 | s.erase(left[b[p].back()]);
| ^~~~
shoes.cpp:49:11: error: reference to 'left' is ambiguous
49 | Add(left[b[p].back()], -1);
| ^~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1006:3: note: candidates are: 'std::ios_base& std::left(std::ios_base&)'
1006 | left(ios_base& __base)
| ^~~~
shoes.cpp:9:21: note: 'std::vector<std::vector<int> > left'
9 | vector<vector<int>> left(N), right(N);
| ^~~~
shoes.cpp:49:21: error: request for member 'back' in 'b.std::vector<int>::operator[](((std::vector<int>::size_type)p))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
49 | Add(left[b[p].back()], -1);
| ^~~~
shoes.cpp:50:7: error: reference to 'right' is ambiguous
50 | right[b[p]].pop_back();
| ^~~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1014:3: note: candidates are: 'std::ios_base& std::right(std::ios_base&)'
1014 | right(ios_base& __base)
| ^~~~~
shoes.cpp:9:30: note: 'std::vector<std::vector<int> > right'
9 | vector<vector<int>> left(N), right(N);
| ^~~~~
shoes.cpp:51:7: error: reference to 'left' is ambiguous
51 | left[b[p]].pop_back();
| ^~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1006:3: note: candidates are: 'std::ios_base& std::left(std::ios_base&)'
1006 | left(ios_base& __base)
| ^~~~
shoes.cpp:9:21: note: 'std::vector<std::vector<int> > left'
9 | vector<vector<int>> left(N), right(N);
| ^~~~
shoes.cpp:53:27: error: reference to 'right' is ambiguous
53 | ans += Get(N) - Get(right[-b[p].back()]) - 1;
| ^~~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1014:3: note: candidates are: 'std::ios_base& std::right(std::ios_base&)'
1014 | right(ios_base& __base)
| ^~~~~
shoes.cpp:9:30: note: 'std::vector<std::vector<int> > right'
9 | vector<vector<int>> left(N), right(N);
| ^~~~~
shoes.cpp:53:39: error: request for member 'back' in 'b.std::vector<int>::operator[](((std::vector<int>::size_type)p))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
53 | ans += Get(N) - Get(right[-b[p].back()]) - 1;
| ^~~~
shoes.cpp:55:15: error: reference to 'right' is ambiguous
55 | s.erase(right[-b[p].back()]);
| ^~~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1014:3: note: candidates are: 'std::ios_base& std::right(std::ios_base&)'
1014 | right(ios_base& __base)
| ^~~~~
shoes.cpp:9:30: note: 'std::vector<std::vector<int> > right'
9 | vector<vector<int>> left(N), right(N);
| ^~~~~
shoes.cpp:55:27: error: request for member 'back' in 'b.std::vector<int>::operator[](((std::vector<int>::size_type)p))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
55 | s.erase(right[-b[p].back()]);
| ^~~~
shoes.cpp:57:11: error: reference to 'right' is ambiguous
57 | Add(right[-b[p].back()], -1);
| ^~~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1014:3: note: candidates are: 'std::ios_base& std::right(std::ios_base&)'
1014 | right(ios_base& __base)
| ^~~~~
shoes.cpp:9:30: note: 'std::vector<std::vector<int> > right'
9 | vector<vector<int>> left(N), right(N);
| ^~~~~
shoes.cpp:57:23: error: request for member 'back' in 'b.std::vector<int>::operator[](((std::vector<int>::size_type)p))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
57 | Add(right[-b[p].back()], -1);
| ^~~~
shoes.cpp:58:7: error: reference to 'right' is ambiguous
58 | right[-b[p]].pop_back();
| ^~~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1014:3: note: candidates are: 'std::ios_base& std::right(std::ios_base&)'
1014 | right(ios_base& __base)
| ^~~~~
shoes.cpp:9:30: note: 'std::vector<std::vector<int> > right'
9 | vector<vector<int>> left(N), right(N);
| ^~~~~
shoes.cpp:59:7: error: reference to 'left' is ambiguous
59 | left[-b[p]].pop_back();
| ^~~~
In file included from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from shoes.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1006:3: note: candidates are: 'std::ios_base& std::left(std::ios_base&)'
1006 | left(ios_base& __base)
| ^~~~
shoes.cpp:9:21: note: 'std::vector<std::vector<int> > left'
9 | vector<vector<int>> left(N), right(N);
| ^~~~