Submission #835193

#	Time	Username	Problem	Language	Result	Execution time	Memory
835193		NeroZein	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	256 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std; 

long long find_maximum(int k, vector<vector<int>> x) {
  int n = x.size();
  int m = x[0].size();
  long long ret = 0; 
  vector<int> tot0(n);
  vector<int> tot1(n); 
  set<array<int, 3>> se; 
  for (int i = 0; i < n; ++i) {
    tot0[i] = count(x[i].begin(), x[i].end(), 0); 
    tot1[i] = m - tot0[i]; 
    se.insert({-tot0[i], tot1[i], i}); 
  }
  vector<int> taken_zeros(n); 
  for (int rep = 0; rep < k; ++rep) {
    int need = 0; 
    int need1 = 0; 
    for (auto [rem0, rem1, idx] : se) {
      rem0 = -rem0;
      if (rem0 > 0 && (rem1 == 0 || need < n / 2)) {
        need++; 
        taken_zeros[idx]++; 
      } else {
        need1++;
      }
    }
    ret += min(need, need1); 
    se.clear(); 
    for (int i = 0; i < n; ++i) {
      se.insert({-(tot0[i] - taken_zeros[i]), tot1[i] - (rep + 1 - taken_zeros[i]), i}); 
    }
  }
  vector<vector<int>> answer(n, vector<int> (m)); 
  for (int i = 0; i < n; ++i) {
    int cnt = 0; 
    for (int j = 0; j < taken_zeros[i]; ++j) {
      answer[i][j] = cnt++;
    }
    int taken_ones = k - taken_zeros[i];
    for (int j = m - taken_ones; j < m; ++j) {
      answer[i][j] = cnt++; 
    }
    assert(cnt == k); 
  }
  allocate_tickets(answer); 
  return ret; 
}

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