Submission #612434

#	Time	Username	Problem	Language	Result	Execution time	Memory
612434		Sam_a17	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1755 ms	348980 KiB

tickets

// #include "A.cpp"
#include <bits/stdc++.h>
// #include <vector>
using namespace std;
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cout << #x << " " << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
#define pb push_back
#define ld long double
#define ll long long
 
// #include "tickets.h"
// #include <vector>
 
void allocate_tickets(vector<vector<int>> a);
 
struct node {
  long long i, j, value;
  
  bool operator!=(const node& other) const {
    return (other.i != i || other.j != j || other.value != value);
  }

  bool operator==(const node& other) const {
    return (other.i == i && other.j == j && other.value == value);
  }

  bool operator<(const node& other) const {
    if(value != other.value) {
      return value < other.value;
    }
    if(i != other.i) {
      return i < other.i;
    }
    return j < other.j;
  }
};
 
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>> answer;
//  dbg(k)
  if(m == 1) {
    vector<vector<int>> answ;
    long long pat = 0;
    vector<long long> values;
    map<long long, int> mp;
    for(int i = 0; i < n; i++) {
      answ.push_back({0});
      values.push_back(x[i][0]);
      mp[x[i][0]]++;
      pat += x[i][0];
    }
 
    sort(all(values));
 
    ll s = INT64_MAX, left = 0, leftCnt = 0;
    for(auto i: mp) {
      leftCnt += i.second;
      left += i.second * i.first;
 
      ll rightCnt = n - leftCnt;
      pat -= i.second * i.first;
 
      s = min(s, leftCnt * i.first - left + pat - rightCnt * i.first);
    }
 
  	allocate_tickets(answ);
    return s;
  } else if(k == m) {
    vector<node> all_members;
    vector<deque<int>> plus_or_minus;
    vector<int> poped_front(n);
 
    plus_or_minus.resize(n);
    answer.resize(n);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        //
        plus_or_minus[i].resize(m);
        answer[i].resize(m);
 
        //
        all_members.push_back({i, j, x[i][j]});
      }
    }
 
    sort(all(all_members));
 
    int mid = (n * m) / 2;
    long long answ = 0;
    for(int i = 0; i < n * m; i++) {
      if(i < mid) {
        plus_or_minus[all_members[i].i][all_members[i].j] = 0;
        answ -= all_members[i].value;
      } else {             
        plus_or_minus[all_members[i].i][all_members[i].j] = 1;
        answ += all_members[i].value;
      }
    }
    
    for(int i = 0; i < m; i++) {
      int plus = n / 2, minus = n / 2;
      vector<node> new_round;
      vector<bool> vis(n);
 
      for(int j = 0; j < n; j++) {
        if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 1 && plus_or_minus[j].back() == 1) {
          int k = plus_or_minus[j].size() - 1 + poped_front[j];
          plus_or_minus[j].pop_back();
          answer[j][k] = i, vis[j] = true;
          plus--;
        }
      }
 
      for(int j = 0; j < n; j++) {
        if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0 && plus_or_minus[j].back() == 0) {
          int k = plus_or_minus[j].size() - 1 + poped_front[j];
          plus_or_minus[j].pop_back();
          answer[j][k] = i, vis[j] = true;
          minus--;
        }
      }
 
      for(int j = 0; j < n; j++) {
        if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j].back() == 1) {
          int k = plus_or_minus[j].size() - 1 + poped_front[j];
          plus_or_minus[j].pop_back();
          answer[j][k] = i, vis[j] = true;
          plus--;
        } else if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0) {
          int k = poped_front[j];
          plus_or_minus[j].pop_front();
          answer[j][k] = i, vis[j] = true;
          poped_front[j]++;
          minus--;
        }
      }
 
      assert(minus == 0 && plus == 0);
    }
 
    allocate_tickets(answer);
    return answ;
  } else {
    vector<vector<node>> all;
    for(int i = 0; i < n; i++) {
      vector<node> row;
      for(int j = 0; j < m; j++) {
        row.push_back({i, j, x[i][j]});
      }
      sort(all(row));
      all.push_back(row);
    }
 
    deque<deque<node>> last_n_k, first_k;

    for(int i = 0; i < n; i++) {
      deque<node> curr_row, curr_st;
 
      for(int j = 0; j < k; j++) {
        curr_row.push_back(all[i][j]);
      }
 
      for(int j = k; j < m; j++) {
        curr_st.push_back(all[i][j]);
      }

      first_k.push_back(curr_row);
      last_n_k.push_back(curr_st);
    }

    // dbg((n * k) / 2)

    priority_queue<pair<long long, int>, vector<pair<long long, int>>> candidates;
    
    for(int j = 0; j < n; j++) {
      if(first_k[j].empty()) continue;
      candidates.push({first_k[j].back().value + last_n_k[j].back().value, j});
    }

    for(int i = 0; i < ((n * k) / 2); i++) {
      int more_valuable = candidates.top().second;
      candidates.pop();
 
      node last = first_k[more_valuable].back();
      last_n_k[more_valuable].pop_back();
      first_k[more_valuable].pop_back();

      last_n_k[more_valuable].push_front(last);

      if(!first_k[more_valuable].empty()) {
        candidates.push({first_k[more_valuable].back().value + last_n_k[more_valuable].back().value, more_valuable});
      }
    }
 
    int all_sz = 0;
    for(int j = 0; j < n; j++) {
      all_sz += sz(first_k[j]);
    }

    assert(all_sz == ((n * k) / 2));
 
    {
      //
      vector<node> all_members;
      vector<deque<int>> plus_or_minus;
      vector<int> poped_front(n);
      map<pair<int, int>, pair<int, int>> mp;
 
      plus_or_minus.resize(n);
      answer.resize(n);
      for(int i = 0; i < n; i++) {
        //
        plus_or_minus[i].resize(k);
        answer[i].resize(k);
 
        int curr_index = 0;
        vector<long long> new_values;
        for(int j = 0; j < sz(first_k[i]); j++) {
          mp[{i, curr_index++}] = {all[i][j].i, all[i][j].j};
          // dbg(all[i][j].value)
          new_values.push_back(all[i][j].value);
        }

        // dbg()
        int cnt = k - sz(first_k[i]);
        for(int j = m - cnt; j < m; j++) {
          // dbg(all[i][j].value)
          mp[{i, curr_index++}] = {all[i][j].i, all[i][j].j};
          new_values.push_back(all[i][j].value);
        }

        sort(all(new_values));
 
        for(int j = 0; j < sz(new_values); j++) {
          all_members.push_back({i, j, new_values[j]});
        }
      }
 
      sort(all(all_members));
 
      int mid = (n * k) / 2;
      long long answ = 0;
      for(int i = 0; i < n * k; i++) {
        if(i < mid) {
          plus_or_minus[all_members[i].i][all_members[i].j] = 0;
          answ -= all_members[i].value;
        } else {             
          plus_or_minus[all_members[i].i][all_members[i].j] = 1;
          answ += all_members[i].value;
        }
      }
      
      for(int i = 0; i < k; i++) {
        int plus = n / 2, minus = n / 2;
        vector<node> new_round;
        vector<bool> vis(n + 1, false);
 
        for(int j = 0; j < n; j++) {
          if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 1 && plus_or_minus[j].back() == 1) {
            int ki = plus_or_minus[j].size() - 1 + poped_front[j];
            plus_or_minus[j].pop_back();
            assert(ki < k);
            answer[j][ki] = i, vis[j] = true;
            plus--;
          }
        }
 
        for(int j = 0; j < n; j++) {
          if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0 && plus_or_minus[j].back() == 0) {
            int ki = plus_or_minus[j].size() - 1 + poped_front[j];
            plus_or_minus[j].pop_back();
            assert(ki < k);
            answer[j][ki] = i, vis[j] = true;
            minus--;
          }
        }
 
        for(int j = 0; j < n; j++) {
          if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j].back() == 1) {
            int ki = plus_or_minus[j].size() - 1 + poped_front[j];
            plus_or_minus[j].pop_back();
            assert(ki < k);
            answer[j][ki] = i, vis[j] = true;
            plus--;
          } else if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0) {
            int ki = poped_front[j];
            plus_or_minus[j].pop_front();
            assert(ki < k);
            answer[j][ki] = i, vis[j] = true;
            poped_front[j]++;
            minus--;
          }
        }
 
        assert(minus == 0 && plus == 0);
      }
 
      vector<vector<int>> answii(n, vector<int> (m, -1));
      for(int i = 0; i < sz(answer); i++) {
        for(int j = 0; j < sz(answer[i]); j++) {
          auto curr_pos = mp[{i, j}];
          assert(curr_pos.first < n && curr_pos.second < m);
          answii[curr_pos.first][curr_pos.second] = answer[i][j];
        }
      }
 
      allocate_tickets(answii);
      return answ;
    }
  }
 
  //
	allocate_tickets(answer);
	return 1;
} 

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10