Submission #349723

#	Time	Username	Problem	Language	Result	Execution time	Memory
349723		MatijaL	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	1137 ms	186388 KiB

tickets

/**
 * Author: MatijaL
 * Time: 2021-01-17 18:15:39
**/
#include <tickets.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define loop(i, n) for(ll i = 0; i < n; i++)
#define FOR(i,n,m) for(ll i = n; i <= m; i++)
#define isIn(vec, item) find(vec.begin(), vec.end(), item) != vec.end()
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define inf 1000000005
#define mod 1000000007
#define print(v) for(auto e : v) cout << e << " "; cout << endl;
#define limit 1600
ll median;
struct Card{
    int color, pos;
    ll num;
    ll worth;
    Card(int a, int b, ll c){
        color = a;
        pos = b;
        num = c;
        worth = abs(num - median);
    }
    bool operator < (const Card& other){
        if(worth!=other.worth) return worth > other.worth;
        return pos < other.pos;
    }
};

ll find_maximum(int K, vector<vector<int>> x){
    int n = x.size();
    int m = x[0].size();
    vector<Card> cards[n];
    vector<ll> allNumbers;
    vector<vector<int>> out(n, vector<int>(m, -1));

    loop(i, n)loop(j, m) allNumbers.pb(x[i][j]);


    sort(all(allNumbers));
    int mid = (m*n)/2 -1;
    median = allNumbers[mid];
    
    loop(i, n)loop(j, m) cards[i].pb(Card(i, j, x[i][j]));

    //printf("MEDIAN is %lld\n", median);

    loop(i, n) sort(all(cards[i])); 


    vector<Card> left[n];
    vector<Card> right[n];
    
    vector<int> pointL(n, 0);
    vector<int> pointR(n, 0);

    //pair<cost, color> right -> subLeft
    vector<pll> subLeft;
    vector<pll> subRight;
    //1. k najboljsih vsake barve
    loop(color, n){
        int cnt = 0;
        int pl = -1;
        int pr = -1;
        for(auto e : cards[color]){
            //printf("Card %d %d %lld\n", e.color, e.pos, e.worth);
            if(cnt < K){
                cnt++;
                if(e.num <= median) left[color].pb(e);
                else right[color].pb(e);
                pl = left[color].size()-1;
                pr = right[color].size()-1;

                pointL[color] = pl;
                pointR[color] = pr;
            }else{
                if(e.num <= median){
                    left[color].pb(e);
                    //probaj dat iz desne
                    if(pr >= 0) subLeft.pb(mp(right[color][pr].worth - e.worth, color));
                    pr--;
                }else{
                    right[color].pb(e);
                    

                    //daj z leve
                    if(pl >= 0) subRight.pb(mp(left[color][pl].worth - e.worth, color));
                    pl--;
                }
            }
            if(pointL[color] > inf) pointL[color] = -1;
            if(pointR[color] > inf) pointR[color] = -1;
        }
    }

    /*
    //printf("Pre-BALANCING\n");
    loop(color, n){
        //printf("Left: ");
        loop(i, pointL[color]+1) //printf("%lld ", left[color][i].num);
        //printf("\n");

        //printf("Right: ");
        loop(i, pointR[color]+1) //printf("%lld ", right[color][i].num);
        //printf("\n");
    }*/

    //2. uravnovesi

    /*
    loop(color, n) //printf("%d %d\n", pointL[color], pointR[color]);

    //printf("SUBSTITUTIONS:\n");
    //printf("Left: ");
    for(auto e : subLeft) //printf("(%lld %lld) ", e.fs, e.sc);
    //printf("\n");
    //printf("Right: ");
    for(auto e : subRight) //printf("(%lld %lld) ", e.fs, e.sc);
    //printf("\n");
    */


    int leftCnt = 0;
    int rightCnt = 0;
    loop(i, n) leftCnt += pointL[i]+1;
    loop(i, n) rightCnt += pointR[i]+1;

    //printf("left cnt %d | right cnt %d\n", leftCnt, rightCnt);

    sort(all(subLeft));
    sort(all(subRight));

         
    for(auto e : subLeft){
        if(leftCnt >= rightCnt) break;
        //printf("one to the left\n");
        int curColor = e.sc;
        leftCnt++;
        rightCnt--;
        pointL[curColor]++;
        pointR[curColor]--;
    }
    for(auto e : subRight){
        if(rightCnt >= leftCnt) break;
        //printf("one to the right\n");
        int curColor = e.sc;
        rightCnt++;
        leftCnt--;
        pointR[curColor]++;
        pointL[curColor]--;
    }
    assert(leftCnt == (n*K)/2 and rightCnt == (n*K)/2);
    /*
    //printf("BALANCING\n");
    loop(color, n){
        //printf("Left: ");
        loop(i, pointL[color]+1) //printf("%lld ", left[color][i].num);
        //printf("\n");

        //printf("Right: ");
        loop(i, pointR[color]+1) //printf("%lld ", right[color][i].num);
        //printf("\n");
    }*/

    ll ans = 0;

    //3 lotimo se dela momci
    loop(k, K){
        //printf("k = %lld assembly: ", k);
        int cl = 0;
        int cr = 0;
        set<int> usedColors;
        
        //nastimaj leve
        loop(color, n){
            if(usedColors.count(color) or pointL[color] < 0) continue;
            if(cl == n/2) break;
            Card c = left[color][pointL[color]];
            pointL[color]--;
            out[c.color][c.pos] = k;
            cl++;
            ans += c.worth;
            usedColors.insert(color);
            //printf("%lld ", c.num);
        }

        //pa se desne
        loop(color, n){
            if(usedColors.count(color) or pointR[color] < 0) continue;
            if(cr == n/2) break;
            Card c = right[color][pointR[color]];
            pointR[color]--;
            out[c.color][c.pos] = k;
            cr++;
            ans += c.worth;
            usedColors.insert(color);
            //printf("%lld ", c.num);
        }
        //printf("\n");
        //assert(cl == n/2 and cr == n/2);
    }

    allocate_tickets(out);
    return ans;
}

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