oj.uz

Submission #432427

# Submission time Handle Problem Language Result Execution time Memory
432427 2021-06-18T09:36:18 Z Amylopectin Carnival Tickets (IOI20_tickets) C++14
0 / 100
 2 ms 844 KB 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include "tickets.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 1610,mxm = 1e7 + 10;
struct ord
{
    int nn,mm,vaa;
};
bool cmp2(const struct ord &l,const struct ord &r)
{
    return l.vaa < r.vaa;
}
struct we
{
    int 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] = {};
int cans[mxn][mxn] = {},coun[mxn] = {},le[mxn] = {},ri[mxn] = {},coub[mxn] = {},fa[mxn] = {};
long long find_maximum(int k, vector<vector<int> > x)
{
	int n = x.size(),i,j,ru = 0,su = 0,rul,rur;
	int 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[n]].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 (int i = 0; i < n; i++)
//	{
//		vector<int> row(m);
//		for (int j = 0; j < m; j++)
//		{
//			if (j < k)
//			{
//				row[j] = j;
//			}
//			else
//			{
//				row[j] = -1;
//			}
//		}
//		answer.push_back(row);
//	}
	allocate_tickets(ans);
	return su;
}
//int main()
//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Incorrect 1 ms 588 KB Contestant returned 18919508441 but the tickets gives a total value of 1739639257
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 440 KB Contestant returned 2727881086 but the tickets gives a total value of -1567086210
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 2 ms 844 KB Contestant returned 1565 but the tickets gives a total value of 1600
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 304 KB Contestant returned 11 but the tickets gives a total value of 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Contestant returned 11 but the tickets gives a total value of 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Contestant returned 11 but the tickets gives a total value of 13
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Incorrect 1 ms 588 KB Contestant returned 18919508441 but the tickets gives a total value of 1739639257
5 Halted 0 ms 0 KB -