Submission #1169110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169110		SmuggingSpun	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	617 ms	100712 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool minimize(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
template<class T>bool maximize(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}
const int lim = 1505;
int n, m, k, a[lim][lim];
namespace sub1{
    ll solve(){
        vector<int>A;
        vector<vector<int>>s(n, vector<int>(m));
        for(int i = 0; i < n; i++){
            A.emplace_back(a[i][0]);
            s[i][0] = 0;
        }
        allocate_tickets(s);
        sort(A.begin(), A.end());
        int median = A[n >> 1];
        ll ans = 0;
        for(int& x : A){
            ans += abs(x - median);
        }
        return ans;
    }
}
namespace sub2{
    ll solve(){
        vector<vector<int>>p(n, vector<int>(2));
        for(int i = 0; i < n; i++){
            if((p[i][0] = min_element(a[i], a[i] + m) - a[i]) == (p[i][1] = max_element(a[i], a[i] + m) - a[i])){
                p[i][0] = 0;
                p[i][1] = 1;
            }
        }
        vector<pair<int, bool>>value;
        for(int i = 0; i < n; i++){
            value.emplace_back(i, false);
            value.emplace_back(i, true);
        }
        sort(value.begin(), value.end(), [&] (auto i, auto j){
            return a[i.first][p[i.first][i.second]] < a[j.first][p[j.first][j.second]];
        });
        vector<pair<int, int>>best;
        ll ans = 0;
        for(int i = 0; i < (n << 1); i++){
            ll sum = -a[value[i].first][p[value[i].first][value[i].second]];
            vector<int>cnt(n, 0);
            vector<bool>use(n, false);
            use[value[i].first] = true;
            vector<pair<int, int>>left, right;
            for(int j = i - 1; j > -1; j--){
                if(++cnt[value[j].first] == 2){
                    left.emplace_back(value[j].first, p[value[j].first][value[j].second]);
                    sum -= a[value[j].first][p[value[j].first][value[j].second]];
                    use[value[j].first] = true;
                }
            }
            fill(cnt.begin(), cnt.end(), 0);
            for(int j = i + 1; j < (n << 1); j++){
                if(++cnt[value[j].first] == 2){
                    right.emplace_back(value[j].first, p[value[j].first][value[j].second]);
                    sum += a[value[j].first][p[value[j].first][value[j].second]];
                    use[value[j].first] = true;
                }
            }
            if(left.size() < (n >> 1) && right.size() <= (n >> 1)){
                vector<int>index, lv(n), rv(n), lp(n), rp(n);
                for(int j = 0; j < i; j++){
                    if(!use[value[j].first]){
                        index.emplace_back(value[j].first);
                        lv[value[j].first] = a[value[j].first][lp[value[j].first] = p[value[j].first][value[j].second]];
                    }
                }
                for(int j = i + 1; j < (n << 1); j++){
                    if(!use[value[j].first]){
                        rv[value[j].first] = a[value[j].first][rp[value[j].first] = p[value[j].first][value[j].second]];
                    }
                }
                int median = a[value[i].first][p[value[i].first][value[i].second]];
                sort(index.begin(), index.end(), [&] (int x, int y){
                    return abs(lv[x] - median) - abs(rv[x] - median) > abs(lv[y] - median) - abs(rv[y] - median);
                });
                for(int j = (n >> 1) - int(left.size()) - 1; j > 0; ){
                    sum -= lv[index[--j]];
                    left.emplace_back(index[j], lp[index[j]]);
                }
                for(int j = (n >> 1) - int(right.size()); j > 0; j--){
                    int t = int(index.size()) - j;
                    sum += rv[index[t]];
                    right.emplace_back(index[t], rp[index[t]]);
                }
                if(maximize(ans, sum)){
                    left.emplace_back(value[i].first, p[value[i].first][value[i].second]);
                    swap(best, left);
                    for(auto& it : right){
                        best.emplace_back(it);
                    }
                }
            }
        }
        vector<vector<int>>s(n, vector<int>(m, -1));
        for(auto& [i, j] : best){
            s[i][j] = 0;
        }
        allocate_tickets(s);
        return ans;
    }
}
namespace sub4{
    ll solve(){
        vector<pair<int, int>>p;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                p.emplace_back(i, j);
            }
        }
        sort(p.begin(), p.end(), [&] (auto i, auto j){
            return a[i.first][i.second] > a[j.first][j.second];
        });
        vector<vector<bool>>big(n, vector<bool>(m, false));
        for(int i = (n * m) >> 1; i > 0; ){
            i--;
            big[p[i].first][p[i].second] = true;
        }
        vector<vector<int>>ans(n, vector<int>(m));
        ll sum = 0;
        deque<pair<int, int>>dq;
        for(int i = 0; i < m; i++){
            dq.emplace_back(n >> 1, i);
        }
        for(int i = 0; i < n; i++){
            for(int t = 0; t < m; t++){
                if(big[i][t]){
                    sum += a[i][t];
                    auto [u, v] = dq.front();
                    dq.pop_front();
                    if(u > 0){
                        dq.emplace_back(u - 1, v);
                    }
                    ans[i][t] = v;
                }
            }
        }
        for(int i = 0; i < n; i++){
            vector<bool>use(m, false);            
            for(int t = 0; t < m; t++){
                if(big[i][t]){
                    use[ans[i][t]] = true;
                }
            }
            vector<int>I;
            for(int t = 0; t < m; t++){
                if(!use[t]){
                    I.emplace_back(t);
                }
            }
            for(int t = 0; t < m; t++){
                if(!big[i][t]){
                    sum -= a[i][t];
                    ans[i][t] = I.back();
                    I.pop_back();
                }
            }
        }
        allocate_tickets(ans);
        return sum;
    }
}
namespace sub3567{
    ll solve(){
        ll sum = 0;
        vector<tuple<int, int, int, int>>greed;
        vector<vector<int>>ans(n, vector<int>(m, -1));
        for(int i = 0; i < n; i++){
            vector<int>p(m);
            iota(p.begin(), p.end(), 0);
            sort(p.begin(), p.end(), [&] (int x, int y){
                return a[i][x] < a[i][y];
            });
            for(int j = 0; j < k; j++){
                sum -= a[i][p[j]];
                ans[i][p[j]] = -2;
                greed.emplace_back(i, p[j], p[m - k + j], j);
            }
        }
        sort(greed.begin(), greed.end(), [&] (auto i, auto j){
            auto& [xi, yi1, yi2, pi] = i;
            auto& [xj, yj1, yj2, pj] = j;
            int sum_i = a[xi][yi1] + a[xi][yi2], sum_j = a[xj][yj1] + a[xj][yj2];
            return sum_i > sum_j || (sum_i == sum_j && pi > pj);
        });
        for(int i = 0; i < ((n * k) >> 1); i++){
            auto [x, y1, y2, foo] = greed[i];
            ans[x][y1] = -1;
            ans[x][y2] = -3;
            sum += a[x][y1] + a[x][y2];
        }
        deque<pair<int, int>>dq;
        for(int i = 0; i < k; i++){
            dq.emplace_back(n >> 1, i);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(ans[i][j] == -3){
                    auto [u, v] = dq.front();
                    dq.pop_front();
                    if(u > 0){
                        dq.emplace_back(u - 1, v);
                    }
                    ans[i][j] = v;
                }
            }
        }
        for(int i = 0; i < n; i++){
            vector<bool>use(k, false);            
            for(int j = 0; j < m; j++){
                if(ans[i][j] > -1){
                    use[ans[i][j]] = true;
                }
            }
            vector<int>I;
            for(int j = 0; j < k; j++){
                if(!use[j]){
                    I.emplace_back(j);
                }
            }
            for(int j = 0; j < m; j++){
                if(ans[i][j] == -2){
                    ans[i][j] = I.back();
                    I.pop_back();
                }
            }
        }
        allocate_tickets(ans);
        return sum;
    }
}
ll find_maximum(int _k, vector<vector<int>>_x){
    n = _x.size();
    m = _x[0].size();
    k = _k;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            a[i][j] = _x[i][j];
        }
    }
    if(m == 1){
        return sub1::solve();
    }
    if(k == 1){
        return sub2::solve();
    }
    if(k == m){
        return sub4::solve();
    }
    return sub3567::solve();
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10