Submission #519099

#	Time	Username	Problem	Language	Result	Execution time	Memory
519099		DanerZein	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	1 ms	204 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
// existen dos escenarios en el que la media sea maxima o en que sea minima

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef pair<ll,ii> iii;
const int MAX_N=1510;
bool vis[MAX_N];
vector<vi> ti;
vector<vi> p1,p0;
ll med;
vector<vi> mat;
int n,m;
ll calcular(vector<ii> id){
  ll s=0;//,s1=0;
  for(int i=0;i<id.size();i++){
    ll val;
    val=mat[id[i].first][id[i].second];
    s+=abs(val-med);
    //s1+=abs(val-pm);
  }
  //s+=abs(pm-med);
  //s1+=abs(pm-med);
  //return min(s,s1);
  return s;
}
bool orden(ii a,ii b){
  return abs(mat[a.first][a.second]-med)>abs(mat[b.first][b.second]-med);
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {

  n=x.size(); m=x[0].size();
  mat=x;
  ti.resize(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++) ti[i].push_back(-1);
  }
  ll ans=0;
  vector<ii> all;
  for(int i=0;i<n;i++){
    all.push_back(ii(i,0));
    all.push_back(ii(i,m-1));
  }
  vector<ii> res;
  for(int i=0;i<2*n;i++){
    ll rp=0;
    int id=all[i].first;
    med=x[id][all[i].second];
    memset(vis,0,sizeof vis);
    vis[id]=1;
    vector<ii> ma,me;
    for(int j=0;j<n;j++){
      if(!vis[j]){
	if(x[j][0]>=med) ma.push_back(ii(j,0));
	if(x[j][0]<=med) me.push_back(ii(j,0));
	if(x[j][m-1]>=med) ma.push_back(ii(j,m-1));
	if(x[j][m-1]<=med) me.push_back(ii(j,m-1));
      }
    }
    sort(ma.begin(),ma.end(),orden);
    sort(me.begin(),me.end(),orden);
    if(ma.size()<(n-2)/2 || me.size()<(n-2)/2) continue;
    vector<ii> o1,o2;
    o1.push_back(all[i]); o2.push_back(all[i]);
    int cma,cme;
    cma=cme=(n-2)/2;
    for(int j=0;j<ma.size();j++){
      if(vis[ma[j].first]) continue;
      o1.push_back(ma[j]);
      cma--;
      vis[ma[j].first]=1;
      if(cma==0) break;
    }
    for(int j=0;j<me.size();j++){
      if(vis[me[j].first]) continue;
      o1.push_back(me[j]);
      cme--;
      vis[me[j].first]=1;
      if(cme==0) break;
    }
    for(int j=0;j<n;j++){
      if(!vis[j]){
	if(abs(x[j][0]-med)>abs(x[j][m-1]-med))
	  o1.push_back(ii(j,0));
	else o1.push_back(ii(j,m-1));
	break;
      }
    }
    if(cma==0 && cme==0)
      rp=calcular(o1);
    cma=cme=(n-2)/2;
    memset(vis,0,sizeof vis); vis[id]=1;
    for(int j=0;j<me.size();j++){
      if(vis[me[j].first]) continue;
      o2.push_back(me[j]);
      cme--;
      vis[me[j].first]=1;
      if(cme==0) break;
    }
    for(int j=0;j<ma.size();j++){
      if(vis[ma[j].first]) continue;
      o2.push_back(ma[j]);
      cma--;
      vis[ma[j].first]=1;
      if(cma==0) break;
    }
    for(int j=0;j<n;j++){
      if(!vis[j]){
	if(abs(x[j][0]-med)>abs(x[j][m-1]-med))
	  o2.push_back(ii(j,0));
	else o2.push_back(ii(j,m-1));
	break;
      }
    }
    if(cma==0 && cme==0)
      rp=max(rp,calcular(o2));
    if(ans<rp){
      ans=rp;
      if(calcular(o1)==calcular(o2)){
	if(cma==0 && cme==0) res=o2;
	else res=o1;
      }
      else{
	if(calcular(o1)==rp) res=o1;
	else res=o2;
      }
    }
  }
  for(int i=0;i<res.size();i++){
    ti[res[i].first][res[i].second]=0;
  }
  allocate_tickets(ti);
  return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'll calcular(std::vector<std::pair<long long int, long long int> >)':
tickets.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i=0;i<id.size();i++){
      |               ~^~~~~~~~~~
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:66:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     if(ma.size()<(n-2)/2 || me.size()<(n-2)/2) continue;
      |        ~~~~~~~~~^~~~~~~~
tickets.cpp:66:38: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     if(ma.size()<(n-2)/2 || me.size()<(n-2)/2) continue;
      |                             ~~~~~~~~~^~~~~~~~
tickets.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=0;j<ma.size();j++){
      |                 ~^~~~~~~~~~
tickets.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int j=0;j<me.size();j++){
      |                 ~^~~~~~~~~~
tickets.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int j=0;j<me.size();j++){
      |                 ~^~~~~~~~~~
tickets.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int j=0;j<ma.size();j++){
      |                 ~^~~~~~~~~~
tickets.cpp:133:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for(int i=0;i<res.size();i++){
      |               ~^~~~~~~~~~~

• 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