Submission #556885

#	Time	Username	Problem	Language	Result	Execution time	Memory
556885		topovik	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	1 ms	696 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>

#ifdef _WIN32
# define I64 "%I64d"
#else
# define I64 "%lld"
#endif

typedef long long ll;

using namespace std;

//static int n;
//static int m;
//static int k;
//static std::vector<std::vector<int> > d;
//static std::vector<std::vector<int> > x;
//static int called = 0;
//
//long long find_maximum(int , std::vector<std::vector<int> > ) ;
//
//
//static void _assert (bool cond, const char* error) {
//    if (!cond) {
//        printf("%s\n", error);
//        exit(0);
//    }
//}
//
//void allocate_tickets (std::vector<std::vector<int> > _d) {
//    _assert(!called, "allocate_tickets called more than once");
//    d = _d;
//    _assert((int) d.size() == n, "allocate_tickets called with parameter of wrong size");
//    for (int i = 0;  i < n;  i++)
//        _assert((int) d[i].size() == m, "allocate_tickets called with parameter of wrong size");
//    called = 1;
//}
//
//int main () {
//    assert(scanf("%d %d %d", &n, &m, &k) == 3);
//    x.resize(n);
//    for (int i = 0;  i < n;  i++) {
//        x[i].resize(m);
//        for (int j=0;  j < m;  j++)
//            assert(scanf("%d", &x[i][j]) == 1);
//    }
//    fclose(stdin);
//
//    long long answer = find_maximum(k, x);
//    _assert(called, "failure to call allocate_tickets");
//    printf(I64 "\n", answer);
//    for (int i = 0;  i < n;  i++) {
//        for (int j = 0;  j < m;  j++) {
//            if (j)
//                printf(" ");
//            printf("%d", d[i][j]);
//        }
//        printf("\n");
//    }
//}






long long find_maximum(int k, std::vector<std::vector<int> > x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int> > ans;
    ans.resize(n);
    for (int i = 0; i < n; i++) ans[i].resize(m);

    for (int i = 0; i < n; i++)
    {
        if (i < n / 2)
        {
            for (int j = 0; j < m; j++)
                if (j < k) ans[i][j] = j;
                else ans[i][j] = -1;
        }
        else
        {
            for (int j = m - 1; j >= 0; j--)
                if (j >= (m - k)) ans[i][j] = m - j - 1;
                else ans[i][j] = -1;
        }
    }
    int a[k][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (ans[i][j] != -1) a[ans[i][j]][i] = x[i][j];
    ll sum = 0;
    for (int i = 0; i < k; i++)
    {
        sort(a[i], a[i] + n);
        for (int j = 0; j < n; j++) sum += abs(a[i][j] - a[i][n / 2]);
    }
	allocate_tickets(ans);
	return sum;
}
/*
2 3 2
0 2 5
1 1 3

4 2 1
5 9
1 4
3 6
2 7
*/

• Subtask 1: 11 / 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