제출 #352446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
352446		MatijaL	카니발 티켓 (IOI20_tickets)	C++14	55 / 100	1381 ms	360156 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(ll a, ll 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){
    ll n = x.size();
    ll 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<ll> pointL(n, -1);//index zadnjega elementa?????
    vector<ll> 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){
        ll cnt = 0;
        ll pl = -1;
        ll 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");
    */
    


    ll leftCnt = 0;
    ll 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");
        ll 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");
        ll 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;

    ll 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