# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
465345 | dattranxxx | Arranging Shoes (IOI19_shoes) | C++14 | 32 ms | 1868 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.
/*
* Author : shora
*/
#include "shoes.h"
#include <bits/stdc++.h>
#define print(_v) for (auto &_ : _v) {cerr << _ << ' ';} cerr << endl;
using namespace std;
using ll = long long;
const int oo = 1e9;
ll n;
namespace task_2 {
map<vector<int>, int> dis;
ll solve(vector<int> a) {
vector<int> fin(a.size());
for (int i = 0; i < n; ++i)
fin[2*i] = i+1, fin[2*i+1] = -i-1;
dis[a] = 0;
queue<vector<int>> q;
q.push(a);
while (!q.empty()) {
vector<int> cur = q.front(); q.pop();
if (cur == fin)
return dis[cur];
int d = dis[cur];
for (int i = 1; i < cur.size(); ++i) {
swap(cur[i], cur[i-1]);
if (!dis.count(cur) || d + 1 < dis[cur]) {
dis[cur] = d + 1;
q.push(cur);
}
swap(cur[i], cur[i-1]);
}
}
return dis[fin];
}
}
namespace task_3 {
bool check(vector<int>& a) {
for (int i = 0; i < n; ++i)
if (a[i] > 0 || a[i] != -a[i+n])
return 0;
return 1;
}
}
long long count_swaps(std::vector<int> a) {
n = a.size() / 2;
if (n == 1) return a[0] > 0;
if (task_3::check(a)) return n * (n-1) / 2;
if (n <= 8) return task_2::solve(a);
return -1;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |