Submission #308691

#	Time	Username	Problem	Language	Result	Execution time	Memory
308691		Peti	Carnival Tickets (IOI20_tickets)	C++14	41 / 100	1231 ms	112380 KiB

tickets

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

using namespace std;

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

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

    table[ind] = 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, pair<int, int>>> sor;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            sor.push_back(make_pair(table[i][j], make_pair(i, j)));

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

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

    for(int i = 0; i < (int)sor.size()/2; i++)
        table2[sor[i].second.first][sor[i].second.second].first = -1;

    vector<int> revT(n);
    for(int i = 0; i < n; i++)
    {
        int j = 0;
        while(j < m && table2[i][j].first == -1)
            j++;
        reverse(table2[i].begin(), table2[i].begin() + j);
        reverse(table[i].begin(), table[i].begin() + j);
        revT[i] = j;
    }

    vector<pair<int, pair<int, pair<int, int>>>> csere;
    int db = 0;
    for(int i = 0; i < n; i++)
    {
        reverse(table[i].begin(), table[i].begin()+min(revT[i], m-k));
        reverse(table2[i].begin(), table2[i].begin()+min(revT[i], m-k));

        int x = 0;
        for(int j = m-k; j < m; j++)
        {
            if(table2[i][j].first == -1)
                db++;
            if(table2[i][j].first == 1 && table2[i][x].first == -1)
            {
                csere.push_back(make_pair(table[i][j] + table[i][x], make_pair(i, make_pair(x, j))));
                x++;
            }
        }


        reverse(table[i].begin(), table[i].begin()+min(revT[i], m-k));
    }

    for(int i = 0; i < n; i++)
    {
        int j = 0;
        while(j < m && table2[i][j].first == -1)
            j++;
        reverse(table[i].begin(), table[i].begin() + j);
    }

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

    int x = 0;
    while(db < n*k/2)
    {
        int a = csere[x].second.first, b = csere[x].second.second.first, c = csere[x].second.second.second;
        swap(table2[a][b], table2[a][c]);
        db++;
        x++;
    }


    int forg = 0;
    for(int i = 0; i < n; i++)
    {
        Forgat(table2, i, k, m, forg);
        for(int j = m-k; j < m; j++)
            if(table2[i][j].first == -1)
                forg++;
        forg %= k;
    }

    vector<vector<int>> answer(n, vector<int>(m));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(j < m-k)
                answer[i][table2[i][j].second] = -1;
            else
                answer[i][table2[i][j].second] = j-m+k;
        }
    }

    long long ret = 0;
    for(int i = 0; i < n; i++)
        for(int j = m-k; j < m; j++)
            ret += (long long)table2[i][j].first * table[i][table2[i][j].second];

    allocate_tickets(answer);

	return ret;
}

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