Submission #308737

#	Time	Username	Problem	Language	Result	Execution time	Memory
308737		Peti	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1018 ms	71320 KiB

tickets

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

using namespace std;

void Forgat(vector<int> &table, int k, int m, int f){
    vector<int> temp(table.size());
    for(int i = 0; i < m; i++)
    {
        if(i < m-k){
            temp[i] = table[i];
            continue;
        }

        int x = ((i-m+k) - f + k)%k + m - k;
        temp[x] = table[i];
    }

    table = temp;

    return;
}

void Forgat2(vector<int> &v, int f)
{
    int n = (int)v.size();
    vector<int> temp(n);
    for(int i = 0; i < n; i++)
        temp[(i-f+n)%n] = v[i];
    v = temp;
    return;
}

long long find_maximum(int k, vector<vector<int>> table) {
    int n = (int)table.size(), m = (int)table[0].size();

    vector<pair<int, int>> sor;
    for(int i = 0; i < n; i++)
        for(int j = m-k; j < m; j++)
            sor.push_back(make_pair(table[i][j] + table[i][j-m+k], i));

    sort(sor.begin(), sor.end());

    vector<int> eltol(n, 0);
    for(int i = 0; i < (int)sor.size()/2; i++)
        eltol[sor[i].second]++;

    vector<vector<int>> table2(n, vector<int>(m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            table2[i][j] = j;

    for(int i = 0; i < n; i++)
        Forgat2(table2[i], eltol[i]);

    int forg = 0;
    for(int i = 0; i < n; i++)
    {
        Forgat(table2[i], k, m, forg);
        forg = (forg+eltol[i])%k;
    }

    vector<vector<int>> answer(n, vector<int>(m, -1));
    for(int i = 0; i < n; i++)
        for(int j = m-k; j < m; j++)
            answer[i][table2[i][j]] = j-m+k;

    long long ret = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < eltol[i]; j++)
            ret -= (long long)table[i][j];
        for(int j = m - k + eltol[i]; j < m; j++)
            ret += (long long)table[i][j];
    }

    allocate_tickets(answer);

	return ret;
}

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