Submission #476816

#	Time	Username	Problem	Language	Result	Execution time	Memory
476816		ponytail	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1090 ms	1868 KiB

shoes

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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) {
    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;
}
void solve() {
    int n = 5; //cin >> n;
    vector<int> v(2*n);
    
    for(int i=0; i<n; i++) v[i] = 1;
    for(int i=n; i<2*n; i++) {
        v[i] = -v[i-n];
    }
    shuffle(v.begin(), v.end(), rng);
    
    //for(int i=0; i<2*n; i++) cin >> v[i];

    if(count_swaps(v) != alt_sol(v)) {
        cout << "wrong answer\n";
        cout << n << "\n";
        for(int x:v)cout<<x<<" ";
        cout<<"\n";
        cout<<"expected "<<alt_sol(v)<<", found "<<count_swaps(v)<<"\n";
        exit(0);
    }
}

Compilation message (stderr)

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