Submission #421231

#	Time	Username	Problem	Language	Result	Execution time	Memory
421231		Monchito	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	1 ms	216 KiB

tickets

#include "tickets.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;
using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll INF = 1e18;

int n, m, K;
vector<vi> answer;
deque<pair<int,ll>> hi, lo;

void add_element(ll x1, ll x2, int pos){
    (x1 == 1)? hi.push_front({x1, pos}) : hi.push_back({x1, pos});
    (x2 == 1)? lo.push_back({x2, pos}) : lo.push_front({x2, pos});
}

pair<ll, ii> calc(int& a, int& b, int i){
    pair<ll, ii> ret;

    while(answer[hi[a].second][m-1] != -1 && a < n) a++;
    while(answer[lo[b].second][0] != -1 && b < n) b++;

    if(i%2 == 0 && answer[hi[a].second][m-1] == -1){
        ret.first = hi[a].first;
        ret.second = { hi[a].second, m-1 };
        return ret;
    }

    if(i%2 == 0 || answer[lo[b].second][0] == -1){
        ret.first = lo[b].first;
        ret.second = { lo[b].second, 0 };
        return ret;
    }

    ret.first = hi[a].first;
    ret.second = { hi[a].second, m-1 };
    return ret;
}

ll find_maximum(int k, vvi x){
	n = x.size();
	m = x[0].size();

	answer = vvi(n, vi(m, -1));
    ll S = 0;

    for(int it = 0; it < k; it++){
        hi.clear(); lo.clear();

        for(int i=0; i<n; i++) add_element(x[i][m-1], x[i][0], i);
        
        int a=0, b=0; ll max_value = -INF, min_value = INF;
        vector<ll> selected(n, -1);
        
        for(int i=0; i<n; i++){
            pair<ll, pair<int,int>> p = calc(a, b, i); 

            answer[p.second.first][p.second.second] = it;
            selected[i] = p.first;
            max_value = max(max_value, p.first);
            min_value = min(min_value, p.first);
        }

        ll s1, s2; s1 = s2 = 0;

        ll mid_floor = (max_value + min_value) / 2;
        ll mid_ceil = (max_value + min_value + 1) / 2;

        for(int i=0; i<n; i++) s1 += abs(selected[i] - mid_floor);
        for(int i=0; i<n; i++) s2 += abs(selected[i] - mid_ceil);

        S += min(s1, s2);
    }

	allocate_tickets(answer);
	return S;
}

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