Submission #550079

#	Time	Username	Problem	Language	Result	Execution time	Memory
550079		neki	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KiB

elephants

#include <bits/stdc++.h>

using namespace std;

#define vc vector
#define ps push_back

const int mm=350;
int n, l;

struct e{
    int i, pos, val, odsek, kok;
    
    e(int i_, int pos_): i(i_), pos(pos_){}
    
    bool operator<(const e& oth){return pos < oth.pos;}
};
vc<e> es;

vc<vc<e*>> dp;

void calcdp(vc<e*>& arr){
    int siz=arr.size(), nas=siz;
    if(siz==0) return;
    for(int i=siz-1;i>=0;--i){
        while((*arr[i]).pos+l<= (*arr[nas-1]).pos) --nas;
        if(nas<siz) (*arr[i]).val=(*arr[nas]).val, (*arr[i]).kok=(*arr[nas]).kok + 1;
        else (*arr[i]).val=(*arr[i]).pos+l, (*arr[i]).kok=1;
    }
}

void build(){
    vc<e*> vsi;
    for(auto v : dp) for(auto u : v ) vsi.push_back(u);
    
    dp.clear();
    for(int ods=0;ods<n;ods+=mm){
        vc<e*> nods;
        for(int i=ods;i<min(n, ods+mm);++i){(*vsi[i]).odsek=ods/mm;nods.ps(vsi[i]);}
        calcdp(nods);
        dp.ps(nods);
    }
}

void init(int N, int L, int* X){
    n=N, l=L+1;
    
    for(int i=0;i<n;++i) es.ps(e(i, X[i]));
    dp.ps({});
    for(int i=0;i<n;++i)dp[0].ps(&es[i]);
    build();
}

void printdp(){
    for(auto&& u:dp){
        for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
    }
}

int update(int ind, int y){
    es[ind].pos=y;
    int nov=dp.size()-1; for(int i=0;i<dp.size();++i) if(dp[i].size()>0 and y<(*(dp[i].back())).pos){nov=i;break;}
    int star = es[ind].odsek;
    if(nov!=star){
    	assert(star<dp.size());
        vc<e*> shrani=dp[star];
        dp[star].clear();
        for(auto v : shrani) if((*v).i != ind) dp[star].ps(v);
        calcdp(dp[star]);
        
        dp[nov].ps(&es[ind]);
    }
    //printdp();
    sort(dp[nov].begin(), dp[nov].end(), [](e* a, e* b){
        return (*a)<(*b);
    });
    calcdp(dp[nov]);
    
    //printdp();
    
    int curpos=-1, ret=0;
    for(auto&& v: dp) if(v.size()>0 and curpos<=(*(v.back())).pos){
        int L=0, R=v.size()-1; //nani
        while(L<R){
            int mid=(L+R)/2;
            if(curpos <= (*v[mid]).pos) R=mid;
            else L=mid+1;
        }
        
        curpos= (*v[L]).val;
        ret+= (*v[L]).kok;
    }
    
    return ret;
}

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000
#define MAX_M 1000000

static int N,L,M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&L,&M));
  for(i=0; i<N; i++)
    my_assert(1==scanf("%d",&X[i]));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}

int main()
{
  int i, ans;

  read_input();
  init(N,L,X);
  for(i=0; i<M; i++) {
    ans = update(ii[i],yy[i]);
    if(ans==sol[i])continue;
      printf("Incorrect.  In %d-th move, answered %d (%d expected).\n",
	     i+1, ans, sol[i]);
    return 0;
  }
  printf("Correct.\n");
  return 0;
}

Compilation message (stderr)

elephants.cpp: In function 'void printdp()':
elephants.cpp:56:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |         for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
      |         ^~~
elephants.cpp:56:82: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   56 |         for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
      |                                                                                  ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:62:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     int nov=dp.size()-1; for(int i=0;i<dp.size();++i) if(dp[i].size()>0 and y<(*(dp[i].back())).pos){nov=i;break;}
      |                                      ~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from elephants.cpp:1:
elephants.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |      assert(star<dp.size());
      |             ~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccdOUOn6.o: in function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'; /tmp/ccvoDtZ3.o:elephants.cpp:(.text+0x5c0): first defined here
/usr/bin/ld: /tmp/ccdOUOn6.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvoDtZ3.o:elephants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status