Submission #433168

#	Time	Username	Problem	Language	Result	Execution time	Memory
433168		Amylopectin	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1123 ms	144232 KiB

tickets

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include "tickets.h"
//#include "grader.cpp"
using namespace std;
const long long mxn = 1610,mxm = 1e7 + 10;
struct ord
{
    long long nn,mm,vaa;
};
bool cmp2(const struct ord &l,const struct ord &r)
{
    return l.vaa < r.vaa;
}
struct we
{
    long long vaa,nn;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.vaa < r.vaa;
}
bool cmp3(const struct we &l,const struct we &r)
{
    return l.nn < r.nn;
}

struct ord po[mxm] = {};
struct we so[mxm] = {},cir[mxn] = {};
long long cans[mxn][mxn] = {},coun[mxn] = {},le[mxn] = {},ri[mxn] = {},coub[mxn] = {},fa[mxn] = {};
long long find_maximum(int k, vector<vector<int> > x)
{
	long long n = x.size(),i,j,ru = 0,su = 0,rul,rur;
	long long m = x[0].size();
	vector<vector<int>> ans;
	vector<int > ro;
	for(i=0; i<n; i++)
	{
        for(j=0; j<m; j++)
        {
            cans[i][j] = -1;
        }
	}
	if(m == k)
	{
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                po[ru] = {i,j,x[i][j]};
                ru ++;
            }
            cir[i].nn = i;
        }
        sort(po,po+ru,cmp2);
        for(i=0; i<ru/2; i++)
        {
            su -= po[i].vaa;
            cir[po[i].nn].vaa ++;
        }
        for(i=ru/2; i<ru; i++)
        {
            su += po[i].vaa;
        }
	}
	else
	{
        for(i=0; i<n; i++)
        {
            for(j=0; j<k; j++)
            {
//                printf("%d\n",x[i][j]);
                so[ru] = {x[i][j] + x[i][m-k+j],i};
                su -= x[i][j];
                ru ++;
            }
            cir[i].nn = i;
        }
        sort(so,so+ru,cmp);
        for(i=0; i<ru/2; i++)
        {
            cir[so[i].nn].vaa ++;
        }
        for(i=ru/2; i<ru; i++)
        {
            su += so[i].vaa;
        }
	}
	sort(cir,cir+n,cmp);
	for(i=0; i<n/2; i++)
	{
        le[i] = cir[i].nn;
    }
    for(i=n/2; i<n; i++)
    {
        ri[i-n/2] = cir[i].nn;
    }
    sort(cir,cir+n,cmp3);
    for(i=0; i<n; i++)
    {
        coub[i] = m-1;
    }
    for(i=0; i<k; i++)
    {
        rul = 0;
        rur = 0;
        for(j=0; j<n; j++)
        {
            if(rul < n/2 && (rur == n/2 || cir[le[rul]].vaa < cir[ri[rur]].vaa))
            {
                fa[j] = le[rul];
                rul ++;
            }
            else
            {
                fa[j] = ri[rur];
                rur ++;
            }
        }
        for(j=0; j<n/2; j++)
        {
            le[j] = fa[j];
            cans[fa[j]][coub[fa[j]]] = i;
            coub[fa[j]] --;
        }
        for(j=n/2; j<n; j++)
        {
            ri[j-n/2] = fa[j];
            cans[fa[j]][coun[fa[j]]] = i;
            coun[fa[j]] ++;
            cir[fa[j]].vaa --;
        }
    }
	for(i=0; i<n; i++)
	{
        ro.clear();
        for(j=0; j<m; j++)
        {
            ro.push_back(cans[i][j]);
        }
        ans.push_back(ro);
	}
//	for (long long i = 0; i < n; i++)
//	{
//		vector<int> row(m);
//		for (long long j = 0; j < m; j++)
//		{
//			if (j < k)
//			{
//				row[j] = j;
//			}
//			else
//			{
//				row[j] = -1;
//			}
//		}
//		answer.push_back(row);
//	}
	allocate_tickets(ans);
	return su;
}
//long long main()
//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

• 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