Submission #999902

#	Time	Username	Problem	Language	Result	Execution time	Memory
999902		KasymK	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1105 ms	337444 KiB

shoes

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ff first
#define ss second

bool check(vector<int> v){
    int n = (int)v.size()/2;
    bool ok = true;
    for(int i = 0; i < n; ++i)
        ok &= (v[2*i] < v[2*i+1] and v[2*i]*(-1) == v[2*i+1]);
    return ok;
}

ll count_swaps(vector<int> v){
    int n = (int)v.size();
    queue<pair<vector<int>, ll>> q;
    vector<vector<int>> vis;
    q.push({v, 0});
    vis.push_back(v);
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        if(check(x.ff))
            return x.ss;
        for(int i = 0; i < n-1; ++i){
            swap(x.ff[i], x.ff[i+1]);
            int ok = 1;
            for(auto i : vis)
                ok &= (i != x.ff);
            if(ok){
                vis.push_back(x.ff);
                q.push({x.ff, x.ss+1});
            }
            swap(x.ff[i], x.ff[i+1]);
        }
    }
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:17:34: warning: control reaches end of non-void function [-Wreturn-type]
   17 |     queue<pair<vector<int>, ll>> q;
      |                                  ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15