Submission #349881

#	Time	Username	Problem	Language	Result	Execution time	Memory
349881		MatijaL	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	1284 ms	221548 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 = 0;
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(num != other.num) return num < other.num;
        if(color != other.color) return color < other.color;
        return pos < other.pos;
    }
};

bool worth_sort(const Card& a, const Card &b){
    if(a.worth!=b.worth) return a.worth > b.worth;
    if(a.color!=b.color) return a.color < b.color;
    return a.pos < b.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) cards[i].pb(Card(i, j, x[i][j]));


    Card medianCard = Card(0,0,0);
    vector<Card> allCards;
    loop(color, n)loop(j, m) allCards.pb(cards[color][j]);
    sort(all(allCards));
    medianCard = allCards[(n*m)/2];
    median = medianCard.num;
    //printf("MEDIAN is %lld\n", median);

    //porihtaj worth
    loop(color, n)loop(j, m) cards[color][j].worth = abs(median - cards[color][j].num);

    //1. k najboljsih vsake barve
    loop(i, n) sort(all(cards[i]), worth_sort); 

    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;
    
    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 < medianCard) 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 < medianCard){
                    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);
    loop(color, n){
        assert(pointR[color]+pointL[color]+2 == K);
    }
    
    /*
    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");
    }*/

    //printf("here\n");

    ll ans = 0;

    int k = 0;
    loop(color, n)loop(j, K){
        Card c = Card(0,0,0);
        if(j < pointL[color]+1) c = left[color][j];
        else c = right[color][j-pointL[color]-1];
        
        out[c.color][c.pos] = k;
        //printf("card %d %d gets %d\n", c.color, c.pos, k);
        k++;
        k %= K;
        ans += c.worth;
    }
    assert(k == 0);



    //3 lotimo se dela momci
    /*
    priority_queue<pll> leftstack;
    priority_queue<pll> rightstack;

    loop(color, n){
        leftstack.push(mp(pointL[color]+1, color));
        rightstack.push(mp(pointR[color]+1, color));
    }

    loop(k, K){
        //printf("k = %lld assembly: ", k);
        int cl = 0;
        int cr = 0;
        set<int> usedColors;
        
        int it =0;


        //nastimaj leve
        while(cl < n/2){
            pll e = leftstack.top();
            leftstack.pop();
            int color = e.sc;
            int amnt = e.fs;

            it++;
            if(it > 10) break;

            printf("left color %d -> amnt %d\n", color, amnt);

            if(usedColors.count(color) or amnt == 0){
                leftstack.push(e);
                continue;
            };
            
            Card c = left[color][amnt-1];
            
            out[c.color][c.pos] = k;
            cl++;
            ans += c.worth;
            usedColors.insert(color);

            leftstack.push(mp(color, amnt-1));
            //printf("%lld ", c.num);
        }

        //pa se desne
        while(cr < n/2){
            pll e = rightstack.top();
            rightstack.pop();
            int color = e.sc;
            int amnt = e.fs;


            it++;
            if(it > 10) break;

            printf("right color %d -> amnt %d\n", color, amnt);

            if(usedColors.count(color) or amnt == 0){
                rightstack.push(e);
                continue;
            };
            
            Card c = right[color][amnt-1];
            
            out[c.color][c.pos] = k;
            cr++;
            ans += c.worth;
            usedColors.insert(color);

            rightstack.push(mp(color, amnt-1));
            //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