Vaihdot

input/code.cpp: In function 'int consume(std::vector<int>&)':
input/code.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(last < v.size()) {
           ~~~~~^~~~~~~~~~
input/code.cpp:10:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v.size(); ++i) {
                        ~~^~~~~~~~~~
input/code.cpp: In function 'int consume2(std::vector<int>&)':
input/code.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); ++i) {
                    ~~^~~~~~~~~~
input/code.cpp:23:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i+1 < pos.size(); ++i) {
                    ~~~~^~~~~~~~~~~~
input/code.cpp: In function 'std::vector<int> brute(std::vector<int>)':
input/code.cpp:29:22: warning: comparison between signed and unsigned integer exp...

#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int consume(vector<int>& v) {
    int last = 0;
    int rounds = 0;
    while(last < v.size()) {
        for(int i = 0; i < v.size(); ++i) {
            if(v[i] == last+1) ++last;
        }
        ++rounds;
    }
    return rounds;
}
int consume2(vector<int>& v) {
    vector<int> pos(v.size());
    for(int i = 0; i < v.size(); ++i) {
        pos[v[i]] = i;
    }
    int inversion_cnt = 0;
    for(int i = 0; i+1 < pos.size(); ++i) {
        if(pos[i] > pos[i+1]) ++inversion_cnt;
    }
    return inversion_cnt+1;
}
vector<int> brute(vector<int> v) {
    for(int i = 0; i < v.size(); ++i) {
        --v[i];
    }
    int min_ans = 1e9;
    int min_cnt = 0;
    int max_ans = 0;
    vector<pair<int, int> > swaps;
    for(int i = 0; i < v.size(); ++i) {
        for(int j = 0; j < i; ++j) {
            swap(v[i], v[j]);
            int rounds = consume2(v);
            swap(v[i], v[j]);
            max_ans = max(max_ans, rounds);
            if(rounds < min_ans) {
                min_ans = rounds;
                min_cnt = 1;
                swaps.clear();
                swaps.push_back({i, j});
            }
            else if(rounds == min_ans) {
                ++min_cnt;
                swaps.push_back({i, j});
            }
        }
    }
    //for(auto x: swaps) cout<<x.first<<' '<<x.second<<'\n';
    return {min_ans, min_cnt, consume2(v), max_ans};
}
struct Event {
    int pos;
    int element;
    int type;
};
bool operator< (const Event& a, const Event& b) {
    if(a.pos == b.pos) {
        return a.type < b.type;
    }
    return a.pos < b.pos;
}
struct SwapEffect {
    int start;
    int end;
    int type;
};
vector<SwapEffect> getSwapEffects(int i, vector<int>& v, vector<int>& pos) {
    vector<SwapEffect> out;
    int p0 = pos[v[i]-1];
    int p1 = pos[v[i]];
    int p2 = pos[v[i]+1];
    int n = v.size();
    // 000+++000
    if(p0 < p2) {
        if(p0 < p1 && p1 < p2) {
            out.push_back({0, p0, 1});
            out.push_back({p0+1, p2, 0});
            out.push_back({p2+1, n-1, 1});
        }
        else {
            out.push_back({0, p0, 0});
            out.push_back({p0+1, p2, -1});
            out.push_back({p2+1, n-1, 0});
        }
    }
    // +++000+++
    else {
        if(p2 < p1 && p1 < p0) {
            out.push_back({0, p2, -1});
            out.push_back({p2+1, p0, 0});
            out.push_back({p0+1, n-1, -1});
        }
        else {
            out.push_back({0, p2, 0});
            out.push_back({p2+1, p0, 1});
            out.push_back({p0+1, n-1, 0});
        }
    }
    return out;
}
class BitVector {
private:
    ull *v;
public:
    BitVector(int n) {
        v = new ull[(n+63)/64]();
    }
    bool get(int pos) {
        return !!(v[pos/64]&(1ull<<(pos&63)));
    }
    void set(int pos, bool value) {
        v[pos/64] ^= (-value^v[pos/64])&(1ull<<(pos&63));
    }
    int sum(int start, int end) {
        --end;
        if(start > end) return 0;
        if(start/64 == end/64) {
            ull tmp = (v[start/64]&(-1ull>>(63-end%64))) & (-1ull<<(start%64));
            return __builtin_popcountll(tmp);
        }
        ull tmp = v[end/64]&(-1ull>>(63-end%64));
        int s = __builtin_popcountll(tmp);//v[start/64]&(-1ull>>(64-end
        tmp = v[start/64]&(-1ull<<(start%64));
        s += __builtin_popcountll(tmp);//v[start/64]&(-1ull>>(64-end
        for(int i = start/64+1; i < end/64; ++i) {
            s += __builtin_popcountll(v[i]);
            //s += !!(v[i/64]&(1ull<<(i%64)));
        }
        return s;
    }
    ~BitVector() {
        delete[] v;
    }
};
vector<ull> solve(vector<int> v) {
    ull ans[5]{};
    vector<Event> events;
    v.insert(v.begin(), 0);
    v.push_back(v.size());
    vector<int> pos(v.size());
    //cout<<"v: "<<endl;
    for(int i = 0; i < v.size(); ++i) {
    //    cout<<v[i]<<' ';
        pos[v[i]] = i;
    }
    //cout<<'\n';
    int n = v.size();
    for(int i = 1; i+1 < v.size(); ++i) {
        auto effects = getSwapEffects(i, v, pos);
      //  cout<<"element: "<<v[i]<<endl;
        for(auto x: effects) {
     //       cout<<"effect: "<<x.start<<' '<<x.end<<' '<<x.type<<endl;
            if(x.type != 0) {
                events.push_back({x.start, i, x.type});
                events.push_back({x.end, i, -x.type});
            }
        }
    }
    sort(events.begin(), events.end());
    /*
    cout<<"events: "<<endl;
    for(auto x: events) {
        cout<<x.pos<<' '<<x.element<<' '<<x.type<<endl;
    }
    cout<<"testing :"<<(events[2]<events[3])<<endl;
    */
    BitVector minus(v.size());
    BitVector plus(v.size());
    int total_minus = 0;
    int total_plus = 0;
    int e_pos = 0;
    for(int i = 1; i+1 < v.size(); ++i) {
         //cout<<'i'<<i<<endl;
        while(e_pos < events.size() && events[e_pos].pos <= i) {
            /*
             cout<<"epos "<<e_pos<<' '<<events.size()<<endl;
             cout<<events[e_pos].element<<endl;
             cout<<events[e_pos].type<<endl;
             cout<<v.size()<<endl;
             */
            if(events[e_pos].type == -1) {
                if(plus.get(events[e_pos].element)) {
                    plus.set(events[e_pos].element,  0);
                    --total_plus;
                }
                else {
                    minus.set(events[e_pos].element, 1);
                    ++total_minus;
                }
            }
            if(events[e_pos].type == 1) {
                if(minus.get(events[e_pos].element)) {
                    minus.set(events[e_pos].element, 0);
                    --total_minus;
                }
                else {
                    plus.set(events[e_pos].element, 1);
                    ++total_plus;
                }
            }
            ++e_pos;
        }
        auto effects = getSwapEffects(i, v, pos);
        for(auto x: effects) {
            x.start = max(i+1, x.start);
            x.end = max(x.start, x.end);
            int plus_sum = plus.sum(x.start, x.end);
            int minus_sum = minus.sum(x.start, x.end);
           // cout<<v[i]<<endl;
           // cout<<"plus and minus: "<<plus_sum<<' '<<minus_sum<<endl;
           // cout<<x.type<<' '<<x.start<<' '<<x.end<<endl;
            ans[2+x.type-1] += minus_sum;
            ans[2+x.type] += x.end - x.start - plus_sum - minus_sum;
            ans[2+x.type+1] += plus_sum;
        }
    }
    //cout<<ans[0]<<' '<<ans[1]<<' '<<ans[2]<<endl;
    for(int i = 1; i+1 < v.size(); ++i) {
        if(v[i]+2 == v.size()) continue;
        int prev = 0;
        for(int j = -1; j <= 1; ++j) {
            prev += pos[v[i]+j+1] < pos[v[i]+j];
        }
        swap(pos[v[i]], pos[v[i]+1]);
        int after = 0;
        for(int j = -1; j <= 1; ++j) {
            after += pos[v[i]+j+1] < pos[v[i]+j];
        }
        swap(pos[v[i]], pos[v[i]+1]);
        //cout<<prev<<' '<<after<<endl;
        ++ans[2+after-prev];
    }
    for(int i = 0; i < 5; ++i) {
        if(ans[i] > 0) {
            vector<ull> out = {(ull)consume2(v)+i-2, ans[i]};
            return out;
        }
    }
    return {};
}
vector<int> read() {
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) {
        cin>>v[i];
    }
    return v;
}
int main() {
    auto ans = solve(read());
    cout<<ans[0]<<' '<<ans[1]<<endl;
    return 0;
    vector<int> v(200000);
    for(int i = 0; i < v.size(); ++i) {
        v[i] = i+1;
    }
    // mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
    mt19937 mt(1337);
    for(int i = 0; i < 10; ++i) {
        shuffle(v.begin(), v.end(), mt);
        //auto ans = brute(v);
        auto ans2 = solve(v);
        cout<<ans2[0]<<' '<<ans2[1]<<endl;
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 2, 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: ACCEPTED

Test 19

Group: 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: ACCEPTED

Test 24

Group: 3

Verdict: ACCEPTED