Submission #476813

#	Time	Username	Problem	Language	Result	Execution time	Memory
476813		ponytail	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1103 ms	421332 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef long long ll;
int n;
int inv(int x){
    if(x<0) return -x;
    else if(x>n) return x - n;
    else return x + n;
}
mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());

ll alt_sol(vector<int> S) {
    map<vector<int>, int> vis;
    map<vector<int>, int> dist;
    dist[S] = 0;
    vector<int> T = S;
    sort(S.begin(), S.end());
    do {
        if(S != T) dist[S] = 1e9;
    } while(next_permutation(S.begin(), S.end()));
    queue<vector<int> > q;
    q.push(T);
    while(q.size()) {
        vector<int> f = q.front(); q.pop();
        vector<int> og = f;
        if(vis[f]) continue;
        vis[f] = 1;
        for(int i=1; i<f.size(); i++) {
            swap(f[i-1], f[i]);
            if(!vis[f] && dist[f] > dist[og] + 1) {
                dist[f] = dist[og] + 1;
                q.push(f);
            }
            swap(f[i-1], f[i]);
        }
    }
    int ans = 1e9;
    for(auto x : dist) {
        int wow = x.first.size() / 2;
        bool ok = 1;
        for(int i=0; i<wow; i++) {
            if(x.first[2*i] > 0 || x.first[2*i+1] < 0) ok = 0; 
            if(abs(x.first[2*i]) != abs(x.first[2*i+1])) ok = 0;
        }
        if(ok) {
            ans = min(ans, x.second);
        }
    }
    return ans;
}

ll count_swaps(vector<int> S) {
  return alt_sol(S);
    int nxt = 0;
    ll ans = 0;
    for(int i=0; i<S.size(); i++) {
        if(S[i] < 0) {
            for(int j=i-1; j>=nxt; j--) {
                swap(S[j], S[j+1]); ans++;
            }
            for(int j=nxt+1; j<S.size(); j++) {
                if(S[j] == -S[nxt]) {
                    for(int k=j-1; k>=nxt+1; k--) {
                        swap(S[k], S[k+1]); ans++;
                    }
                    break;
                }
            }
            nxt += 2;
        }
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'll alt_sol(std::vector<int>)':
shoes.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=1; i<f.size(); i++) {
      |                      ~^~~~~~~~~
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~
shoes.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int j=nxt+1; j<S.size(); j++) {
      |                              ~^~~~~~~~~

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