Submission #476851

#	Time	Username	Problem	Language	Result	Execution time	Memory
476851		ponytail	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1093 ms	75228 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) break;
        }
        if(ok) {
            ans = min(ans, x.second);
        }
    }
    return ans;
}

ll count_swaps(vector<int> S) {
    ll ans = 0;
    int lb = 0;
    while(lb < S.size()) {
        map<int, queue<int> >mp;
        for(int i=lb; i<S.size(); i++) {
            if(S[i] < 0) {
                mp[-S[i]].push(i);
            }
        }
        int partner[S.size()];
        for(int i=lb; i<S.size(); i++) {
            if(S[i] > 0) {
                partner[i] = mp[S[i]].front();
                partner[mp[S[i]].front()] = i;
                mp[S[i]].pop();
            }
        }
        int idx = -1;
        int wow = 1e9;
        for(int i=lb; i<S.size(); i++) {
            if(S[i] > 0) {
                if(partner[i] > i) {
                    if(partner[i] + i < wow) {
                        wow = partner[i] + i; idx = i;
                    }
                }
                else {
                    if(partner[i] + i - 1 < wow) {
                        wow = partner[i] + i - 1; idx = i;
                    }
                }
            }
        }
        ans += wow - 2 * lb;
        for(int i=partner[idx]-1; i>=lb; i--) {
            swap(S[i], S[i+1]);
        }
        for(int i=idx-(partner[idx] < idx); i>=lb+1; i--) {
            swap(S[i], S[i+1]);
        }
        lb += 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:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while(lb < S.size()) {
      |           ~~~^~~~~~~~~~
shoes.cpp:59:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=lb; i<S.size(); i++) {
      |                       ~^~~~~~~~~
shoes.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i=lb; i<S.size(); i++) {
      |                       ~^~~~~~~~~
shoes.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int i=lb; i<S.size(); i++) {
      |                       ~^~~~~~~~~

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