Submission #304350

#	Time	Username	Problem	Language	Result	Execution time	Memory
304350		AlanC	Carnival Tickets (IOI20_tickets)	C++14	Compilation error	0 ms	0 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <queue>
#define N 1505
using namespace std;

int n, m, k, cnt = 0, low[N], high[N], used[N];
vector<vector<int>> answer, a;
long long int total = 0;

struct Dat {
	long long int sum;
	int col, pos;
	
	Dat(){}
	
	Dat(long long int s, int c, int p) {
		sum = s;
		col = c;
		pos = p;
	}
	bool operator < (const Dat &d) {
		return sum < d.sum;
	}
} D[N * N];


vector<pair<int, int>> small, large;

void prepDat() {
	for (int i=0; i<n; i++) {
		for (int j=0; j<k; j++) {
			D[cnt++] = Dat(a[i][j] + a[i][m-k+j], i, j);
		}
	}
}

void generateAnswer() {
	for (int i=0; i<n; i++) low[i] = 0;
	for (int i=0; i<cnt/2; i++)
		low[D[i].col] = max(low[D[i].col], D[i].pos + 1);

	for (int i=0; i<n; i++) high[i] = k - low[i];
	
	small.clear(); large.clear();
	
	for (int i=0; i<n; i++) if (low[i] > 0) small.push_back(make_pair(low[i], i));
	for (int i=0; i<n; i++) if (high[i] > 0) large.push_back(make_pair(high[i], i));
	
	for (int i=0; i<n; i++) {
		vector<int> row(m, -1);
		answer.push_back(row);
		printf("[%d] %d %d\n", i, low[i], high[i]);
	}

	
	for (int i=0; i<k; i++) {
		for (int j=0; j<n; j++) used[j] = 0;
		int x = 0, y = 0;
		for (int j=0; j<n/2; j++) {
		
			while (used[small[x].second] && x < small.size()) x++;
			used[small[x].second] = 1;
			while (used[large[y].second] && y < large.size()) y++;
			if (x == small.size() - 2 && y == large.size() - 2 && small[x + 1].second == large[y + 1].second)
				swap(large[y], large[y + 1]);
			used[large[y].second] = 1;
			
			
			int c1 = small[x].second, c2 = large[y].second;
			int p1 = small[x].first - 1, p2 = m - large[y].first;
			//printf("[%d %d], [%d %d]\n", c1, p1, c2, p2);
			
			answer[c1][p1] = i;
			answer[c2][p2] = i;
			total += a[c2][p2] - a[c1][p1];
			low[c1]--;
			high[c2]--;
		}
		
		small.clear();
		large.clear();
		
		for (int j=0; j<n; j++) if (low[j] > 0) small.push_back(make_pair(low[j], j));
		for (int j=0; j<n; j++) if (high[j] > 0) large.push_back(make_pair(high[j], j));
		
		sort(small.begin(), small.end(), greater());
		sort(large.begin(), large.end(), greater());
	}
	
	
}


long long find_maximum(int K, vector<vector<int>> x) {
	n = x.size();
	m = x[0].size();
	k = K;
	a = x;
	
	prepDat();
	
	sort(D, D + cnt);
	
	generateAnswer();
	
	allocate_tickets(answer);
	return total;
}

Compilation message (stderr)

tickets.cpp: In function 'void generateAnswer()':
tickets.cpp:54:3: error: 'printf' was not declared in this scope
   54 |   printf("[%d] %d %d\n", i, low[i], high[i]);
      |   ^~~~~~
tickets.cpp:5:1: note: 'printf' is defined in header '<cstdio>'; did you forget to '#include <cstdio>'?
    4 | #include <queue>
  +++ |+#include <cstdio>
    5 | #define N 1505
tickets.cpp:63:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    while (used[small[x].second] && x < small.size()) x++;
      |                                    ~~^~~~~~~~~~~~~~
tickets.cpp:65:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    while (used[large[y].second] && y < large.size()) y++;
      |                                    ~~^~~~~~~~~~~~~~
tickets.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    if (x == small.size() - 2 && y == large.size() - 2 && small[x + 1].second == large[y + 1].second)
      |        ~~^~~~~~~~~~~~~~~~~~~
tickets.cpp:66:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    if (x == small.size() - 2 && y == large.size() - 2 && small[x + 1].second == large[y + 1].second)
      |                                 ~~^~~~~~~~~~~~~~~~~~~
tickets.cpp:88:43: error: missing template arguments before '(' token
   88 |   sort(small.begin(), small.end(), greater());
      |                                           ^
tickets.cpp:89:43: error: missing template arguments before '(' token
   89 |   sort(large.begin(), large.end(), greater());
      |                                           ^