제출 #607636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
607636		APROHACK	Dancing Elephants (IOI11_elephants)	C++14	0 / 100	1 ms	340 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
ll n, mn, mx, l, blocksz;
vector<pair<ll, ll> >a;
map<int, pair<int, pair<int, int> > > value; // indx a has a value of b, in indx b.ss.ff, and block b.ss.ss
multiset<int>blocks[400];
int theBlockIsUpTo[400], theBlockIsUpToComenzandoen[400][1200], ansBlock[400], ansBlockComenzandoen[400][1200]; // bloque, start
int calculateBlock(int blc, int start){
  vector<int>vc;
  cout<<"bloque "<<blc << endl<<endl;
  for(auto i : blocks[blc]){
    vc.pb(i);
  }
  int desdeReal = *blocks[blc].upper_bound(start);
  if(desdeReal < start)desdeReal=-1;
  for(int i = 0 ; i < vc.size() ; i++){
    cout << i << " i " << vc[i] <<endl;
    int currentCam = vc[i], cuenta=1;
    for(int j = i ; j < vc.size() ; j++){
      if(currentCam+l<vc[j]){
        currentCam=vc[j];
        cuenta++;
      }
    }
    
    theBlockIsUpToComenzandoen[blc][i] = currentCam + l;
    ansBlockComenzandoen[blc][i] = cuenta;
    cout << " " << theBlockIsUpToComenzandoen[blc][i] << " " << ansBlockComenzandoen[blc][i] << endl;
    if(vc[i] == desdeReal){
      theBlockIsUpTo[blc] = currentCam+l;
      ansBlock[blc] = cuenta;
    }
  }
  return theBlockIsUpTo[blc];
}
void upd(){
  int curr = 0, st = 0;
  sort(a.begin(), a.end());
  for(int i  = 0 ;  i < n ; i++){
    
    if(curr++==blocksz){
      st++;
      curr=0;
    }
    value[a[i].ss] = {a[i].ff, {i, st}};
    blocks[st].insert(a[i].ff);
  }
  int last = -1;
  for(int i = 0 ; i  <= st ; i++){
    last = calculateBlock(i, last);
  }
  
}
void init(int N, int L, int X[])
{
  n = N, l = L;
  blocksz = sqrt(n);
  cout<<blocksz<<endl;
  for(int i = 0 ; i < n ; i++){
    a.pb({X[i], i});
  }
  upd();
}

int update(int i, int y)
{
  //a[value[i].ss.ff]={y, {a[value[i]].ss}};
  ll cuenta = 1, curr = a[0].ff;
  for(int i = 1 ; i < n ; i ++){
    if(curr+l >= a[i].ff)continue;
    cuenta++;
    curr = a[i].ff  ;
  }
  return cuenta;
}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'int calculateBlock(int, int)':
elephants.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i = 0 ; i < vc.size() ; i++){
      |                   ~~^~~~~~~~~~~
elephants.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j = i ; j < vc.size() ; j++){
      |                     ~~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3