Submission #352444

#	Time	Username	Problem	Language	Result	Execution time	Memory
352444		MatijaL	Carnival Tickets (IOI20_tickets)	C++14	55 / 100	1366 ms	359932 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{
    ll 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;
    ll preMedian = allCards[(n*m)/2 - 1].num;
    bool shiftingEnabled = preMedian == median;
    //printf("MEDIAN is %lld %lld\n", median, preMedian);

    //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, -1);//index zadnjega elementa?????
    vector<int> pointR(n, -1);

    //pair<cost, color> right -> subLeft
    vector<pll> subLeft;
    vector<pll> subRight;
    

    /*

    Od vsake barve izberi k najboljsih elementov
    Opiši kakšne so cene tega, 
    da se odpoveš elementu na eni strani za slabši elemnt na drugi

    Upoštevaj da lahko element ki je enak mediani uporabiš na obeh straneh!



    */
    loop(color, n){
        int cnt = 0;
        int pl = -1;
        int pr = -1;
        vector<Card> medianRight;
        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 and shiftingEnabled){
                    ////
                    left[color].pb(e);
                    medianRight.pb(e);

                    //upostevaj samo levega
                    pointL[color] = left[color].size()-1;

                    //printf("Median card found\n");
                    subRight.pb(mp(0, color));
                    continue;
                }


                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.num == median and shiftingEnabled){
                    //poponoma neuporabno
                    left[color].pb(e);
                    //probaj dat iz desne
                    if(pr >= 0) subLeft.pb(mp(right[color][pr].worth - e.worth, color));
                    pr--;


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

                }
                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;

            
        }
        reverse(all(medianRight));
        for(auto e : medianRight) right[color].pb(e);
    }

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

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

    }*/

    //2. uravnovesi

    
    
    /*
    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;
        if(pointR[curColor] == -1) continue;
        leftCnt++;
        rightCnt--;
        pointL[curColor]++;
        pointR[curColor]--;
    }
    for(auto e : subRight){
        if(rightCnt >= leftCnt) break;
        //printf("one to the right\n");
        int curColor = e.sc;
        if(pointL[curColor] == -1) continue;
        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].pos);
        printf("\n");

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

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

    ll ans = 0;

    int k = 0;
    loop(color, n)loop(j, pointL[color]+1){
        Card c = left[color][j];
        
        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);

    for(int color = n-1; color >= 0; color--)loop(j, pointR[color]+1){
        Card c = right[color][j];
        
        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: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10