Submission #1024140

#TimeUsernameProblemLanguageResultExecution timeMemory
1024140TheWilpCarnival Tickets (IOI20_tickets)C++14
11 / 100
3074 ms860 KiB
#include "tickets.h" #include <vector> #include <algorithm> using ll = long long; class name { public: int value; int i,j; bool operator<(const name& other) const { return value < other.value; } }; 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(N,std::vector<int>(M,-1)); std::vector<int> group(N,0); std::vector<std::vector<int>> round(k); std::vector<name> s; for(int q = 0;q < N;q++) { for(int w = 0;w < M;w++) { name n; n.value = x[q][w]; n.i = q; n.j = w; s.push_back(n); } } std::sort(s.begin(),s.end()); int i = s.size() - 1; int t = 0; std::vector<std::vector<name>> upper(N); while(i >= 0 && t < k * N / 2) { name e = s[i--]; if(group[e.i] >= k) continue; upper[e.i].push_back(e); group[e.i]++; t++; } i = 0; t = 0; std::vector<std::vector<name>> lower(N); for(int q = 0;q < N;q++) { while(group[q] < k) { name n; n.i = q; n.j = group[q]; n.value = x[q][group[q]++]; lower[q].push_back(n); } } int r = 0; int j = 0; std::vector<int> start_pos(N); while(j < upper.size()) { for(int q = 0;q < upper[j].size();q++) { round[r].push_back(upper[j][q].value); ans[upper[j][q].i][upper[j][q].j] = r; ++r; r%=k; } start_pos[j] = r; ++j; } for(int q = 0;q < N;q++) { int rr = start_pos[q] + lower[q].size(); if(rr % k != start_pos[q] % k) { while(true) { int * bb = new int[10000000]; } } } r = 0; j = 0; while(j < lower.size()) { r = start_pos[j]; for(int q = 0;q < lower[j].size();q++) { round[r].push_back(lower[j][q].value); ans[lower[j][q].i][lower[j][q].j] = r; ++r; r%=k; } ++j; } ll res = 0; for(int q = 0;q < k;q++) { std::sort(round[q].begin(),round[q].end()); for(int w = 0;w < N / 2;w++) { res -= round[q][w]; } for(int w = N / 2;w < N;w++) { res += round[q][w]; } } allocate_tickets(ans); return res; }

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:61:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<name> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  while(j < upper.size()) {
      |        ~~^~~~~~~~~~~~~~
tickets.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<name>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int q = 0;q < upper[j].size();q++) {
      |                 ~~^~~~~~~~~~~~~~~~~
tickets.cpp:76:11: warning: unused variable 'bb' [-Wunused-variable]
   76 |     int * bb = new int[10000000];
      |           ^~
tickets.cpp:83:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<name> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  while(j < lower.size()) {
      |        ~~^~~~~~~~~~~~~~
tickets.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<name>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int q = 0;q < lower[j].size();q++) {
      |                 ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...