Submission #832146

#TimeUsernameProblemLanguageResultExecution timeMemory
832146tranxuanbachArranging Shoes (IOI19_shoes)C++17
10 / 100
1096 ms114044 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define isz(a) ((signed)a.size()) using ll = long long; const int N = 1e5 + 5; int n; int a[N]; namespace subtask12{ bool check(){ return n <= 8; } map <vector <int>, int> dist; ll solve(){ queue <pair <int, vector <int>>> qu; auto transition = [&](int d, const vector <int>& state){ if (not dist.count(state)){ dist[state] = d; qu.emplace(d, state); } }; transition(0, vector <int>(a + 1, a + 2 * n + 1)); while (not qu.empty()){ auto [d, b] = qu.front(); qu.pop(); bool ok = true; for (int i = 0; i < n; i++){ if (not (b[2 * i] < 0 and b[2 * i] == -b[2 * i + 1])){ ok = false; break; } } if (ok){ return d; } for (int i = 1; i < 2 * n; i++){ swap(b[i - 1], b[i]); transition(d + 1, b); swap(b[i - 1], b[i]); } } } } ll count_swaps(vector <int> _a){ n = isz(_a) / 2; for (int i = 1; i <= 2 * n; i++){ a[i] = _a[i - 1]; } if (subtask12::check()){ return subtask12::solve(); } }

Compilation message (stderr)

shoes.cpp: In function 'll subtask12::solve()':
shoes.cpp:23:36: warning: control reaches end of non-void function [-Wreturn-type]
   23 |   queue <pair <int, vector <int>>> qu;
      |                                    ^~
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...