Submission #1210318

#TimeUsernameProblemLanguageResultExecution timeMemory
1210318madamadam3Arranging Shoes (IOI19_shoes)C++20
10 / 100
1129 ms1078712 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; struct State { vector<pair<int, int>> swaps; int moves; }; bool check_valid(State &state, vector<int> &initial) { vector<int> arrangement = initial; for (auto &el : state.swaps) { swap(arrangement[el.first], arrangement[el.second]); } bool valid = true; for (int i = 0; i < n; i++) { valid = valid && (abs(arrangement[2*i]) == abs(arrangement[2*i+1])) && (arrangement[2*i] < 0 && arrangement[2*i+1] > 0); } return valid; } // left shoe if s[i] < 0 // right shoe if s[i] > 0 ll count_swaps(vector<int> s) { n = s.size() / 2; int minimum = 0; queue<State> q; State best; q.push(State{{}, 0}); while (!q.empty()) { State cur = q.front(); q.pop(); if (check_valid(cur, s)) { minimum = cur.moves; best = cur; break; } for (int i = 1; i < 2*n; i++) { for (int j = i-1; j < i+2 && j < 2*n; j++) { if (i == j) continue; vector<pair<int, int>> swaps = cur.swaps; swaps.push_back({i, j}); q.push(State{swaps, cur.moves + 1}); } } } // cout << "Fastest fix is " << best.moves << " moves\n"; // for (auto &el : best.swaps) { // cout << "Swapped " << el.first << " and " << el.second << "\n"; // } return minimum; }
#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...