Submission #132061

#	Time	Username	Problem	Language	Result	Execution time	Memory
132061		dragonslayerit	Fish (IOI08_fish)	C++14	49 / 100	3098 ms	43524 KiB

fish

#include <cstdio>
#include <algorithm>
#include <vector>

//Strategy:
//Sort fishes by size
//Relabel gems by last appearance (e.g. gem of largest fish is 0)
//count multisets of gems => count multisets of fish such that if a fish is chosen, all smaller fish with same gem are chosen
//For the actual subset of fish, some gem will be chosen to be "boosted" to the largest fish with that gem.
//Iterate over last fish in multiset (pre-boosting) and count number of valid subsets
//A multiset is bad iff no gem in the prefix is present and the largest fish's gem cannot be boosted.

int cps[500005];
int cps_size=0;

int freq[500005];
int freq2[500005];
int last[500005];

int half[500005];
int prev[500005];

struct Fish{
  int size,gem;
  bool operator<(Fish f)const{
    return size<f.size;
  }
}fishes[500005];

struct Op{
  int sgn;
  int l,r,x;
  Op(int sgn,int l,int r,int x):sgn(sgn),l(l),r(r),x(x){
  }
};

std::vector<Op> ops[500005];

int main(){
  int N,K,MOD;
  scanf("%d %d",&N,&K);
  scanf("%d",&MOD);
  for(int i=0;i<N;i++){
    scanf("%d %d",&fishes[i].size,&fishes[i].gem);
    fishes[i].gem--;
  }
  std::sort(fishes,fishes+N);
  //Relabel gems by last appearance
  std::fill(cps,cps+K,-1);
  for(int i=N-1;i>=0;i--){
    if(cps[fishes[i].gem]==-1){
      cps[fishes[i].gem]=cps_size++;
    }
  }
  for(int i=0;i<N;i++){
    fishes[i].gem=cps[fishes[i].gem];
  }
  for(int k=0;k<K;k++){
    last[k]=-1;
  }
  for(int i=0;i<N;i++){
    prev[i]=last[fishes[i].gem];
    last[fishes[i].gem]=i;
    //printf("prev[%d]=%d\n",i,prev[i]);
  }
  /*
    for(int i=0;i<N;i++){
    printf("i=%d size=%d gem=%d\n",i,fishes[i].size,fishes[i].gem);
    }
  */

  for(int k=0;k<K;k++){
    int low=-1,high=N;
    while(high-low>1){
      int mid=(low+high)/2;
      if(fishes[mid].size*2<=fishes[last[k]].size){
	low=mid;
      }else{
	high=mid;
      }
    }
    half[k]=high;
    //half[k] is index of first fish larger than fishes[last[k]].size/2
    //for(int& j=half[k]=0;fishes[j].size*2<=fishes[last[k]].size;j++);
  }
  
  int ans=0;
  int prefix=K-1;//largest gem # that can be "boosted"
  for(int i=0;i<N;i++){
    while(prefix>=0&&fishes[last[prefix]].size<2*fishes[i].size) prefix--;

    
    //freq[fishes[i].gem]++;
    //Counting configurations where fishes[i].gem occurs exactly freq[fishes[i].gem] times
    //Subtract multisets where none in prefix exist to be boosted
    {
      ops[i+1].emplace_back(-1,prefix+1,K,fishes[i].gem);
      /*
      int product=1;
      for(int k=prefix+1;k<K;k++){
	if(k==fishes[i].gem) continue;
	product=1LL*product*(freq[k]+1)%MOD;
      }
      ans=(ans+MOD-product)%MOD;
      */
    }
    //Add back multisets where none in prefix exist to be boosted but fishes[i] can be boosted
    if(prev[i]!=-1&&fishes[prev[i]].size*2>fishes[last[fishes[i].gem]].size){
      //Impossible because merely taking all of fishes[i].gem violates constraints
      continue;
    }
    
    //using frequencies from last fish whose size <=1/2*size of last fish with fishes[i].gem
    ops[std::min(i,half[fishes[i].gem])].emplace_back(1,prefix+1,K,fishes[i].gem);
    /*{
      std::fill(freq2,freq2+K,0);
      for(int j=0;j<std::min(i,half[fishes[i].gem]);j++){
	freq2[fishes[j].gem]++;
      }
      int product=1;
      for(int k=prefix+1;k<K;k++){
	if(k==fishes[i].gem) continue;
	product=1LL*product*(freq2[k]+1)%MOD;
      }
      ans=(ans+product)%MOD;
    }
    */
  }
  for(int i=0;i<=N;i++){
    //printf("i=%d\n",i);
    for(Op op:ops[i]){
      int product=1;
      for(int k=op.l;k<op.r;k++){
	if(k==op.x) continue;
	product=1LL*product*(freq[k]+1)%MOD;
      }
      //printf("Ans +=%d\n",op.sgn*product);
      ans=(ans+op.sgn*product)%MOD;
    }
    if(i==N) break;
    freq[fishes[i].gem]++;
  }
  //Count all multisets and subtract bad ones
  int all=1;
  for(int k=0;k<K;k++){
    all=1LL*all*(freq[k]+1)%MOD;
  }
  //-1 for empty set
  ans=(ans+all+MOD-1)%MOD;
  printf("%d\n",ans);
  return 0;
}

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&K);
   ~~~~~^~~~~~~~~~~~~~~
fish.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&MOD);
   ~~~~~^~~~~~~~~~~
fish.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&fishes[i].size,&fishes[i].gem);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5