oj.uz

Submission #132016

# Submission time Handle Problem Language Result Execution time Memory
132016 2019-07-18T08:03:46 Z dragonslayerit Fish (IOI08_fish) C++14
32 / 100
 3000 ms 6392 KB 
#include <cstdio>
#include <algorithm>

//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];

struct Fish{
  int size,gem;
  bool operator<(Fish f)const{
    return size<f.size;
  }
}fishes[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 i=0;i<N;i++){
    last[fishes[i].gem]=i;
  }
  /*
  for(int i=0;i<N;i++){
    printf("i=%d size=%d gem=%d\n",i,fishes[i].size,fishes[i].gem);
  }
  */
  int ans=0;
  int prefix=K-1;//largest gem # that can be "boosted"
  for(int i=0;i<N;i++){
    freq[fishes[i].gem]++;
    while(prefix>=0&&fishes[last[prefix]].size<2*fishes[i].size) prefix--;
    //printf("i=%d boostable gem prefix=[0,%d]\n",i,prefix);
    //Counting configurations where fishes[i].gem occurs exactly freq[fishes[i].gem] times (max)
    for(int k=0;k<=prefix;k++){
      if(k==fishes[i].gem) continue;
      //Ignoring fishes[i].gem:
      //k is smallest gem # that can be "boosted" in this configuration
      //gems with smaller # cannot be present
      //gem k must have at least 1
      //gems with larger # can have any amount
      int product=freq[k];
      //printf("i=%d boost %d: %d",i,k,freq[k]);
      for(int g=k+1;g<K;g++){
	if(g==fishes[i].gem) continue;
	product=1LL*product*(freq[g]+1)%MOD;
	//printf("x%d",freq[g]+1);
      }
      //printf("\n");
      ans=(ans+product)%MOD;
    }
    //no gem # can be boosted except fishes[i].gem
    //no gems with #<=prefix (except maybe fishes[i].gem)
    //using frequencies from last fish whose size <=1/2*size of last fish with fishes[i].gem
    std::fill(freq2,freq2+K,0);
    int j;
    for(j=0;j<i&&fishes[j].size*2<=fishes[last[fishes[i].gem]].size;j++){
      freq2[fishes[j].gem]++;
    }
    j--;
    int prefix2=K-1;
    while(prefix2>=0&&last[prefix2-1]<2*fishes[j].size) prefix2--;
    //printf("i=%d j=%d boostable gem prefix2=[0,%d]\n",i,j,prefix2);
    if(freq2[fishes[i].gem]!=freq[fishes[i].gem]-1){
      //printf("Fail: second largest with same gem as i is too big\n");
      continue;
    }
    int product=1;
    //printf("i=%d: 1",i);
    for(int g=prefix+1;g<K;g++){
      if(g==fishes[i].gem) continue;
      product=1LL*product*(freq2[g]+1)%MOD;
      //printf("x%d",freq2[g]+1);
    }
    //printf("\n");
    ans=(ans+product)%MOD;
  }
  printf("%d\n",ans);
  return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:28: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:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&MOD);
   ~~~~~^~~~~~~~~~~
fish.cpp:31: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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Correct 4 ms 376 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Execution timed out 3093 ms 4856 KB Time limit exceeded

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 504 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 376 KB Output is correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3097 ms 2552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 376 KB Output is correct
2 Execution timed out 3032 ms 516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3016 ms 3400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 4828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3033 ms 3460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 4616 KB Time limit exceeded

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 4988 KB Time limit exceeded

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 4472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3009 ms 5732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3030 ms 5588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 6392 KB Time limit exceeded
2 Halted 0 ms 0 KB -