oj.uz

Submission #519654

# Submission time Handle Problem Language Result Execution time Memory
519654 2022-01-26T23:56:02 Z DanerZein Packing Biscuits (IOI20_biscuits) C++14
21 / 100
 1000 ms 332 KB 
#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5;
ll bits[62];
long long count_tastiness(long long x, std::vector<long long> a) {
  if(x!=1){
    ll res=0;
    for(ll i=0;i<=MAX_N;i++){
      memset(bits,0,sizeof bits);
      for(int j=0;j<a.size();j++) bits[j]=a[j];
      bool sw=1;
      for(ll j=0;j<30;j++){
	if(i&(1<<j)){
	  if(bits[j]<x){
	    sw=0;
	    break;
	  }
	  bits[j]-=x;
	}
	bits[j+1]+=(bits[j]/2);
      }
      res+=sw;
    }
    return res;
  }
  memset(bits,0,sizeof bits);
  for(int i=0;i<a.size();i++)
    bits[i]=a[i];
  for(ll j=0;j<=60;j++){
    if(bits[j]>2){
      ll y;
      if(bits[j]%2==0) y=(bits[j]-2)/2;
      else y=(bits[j]-1)/2;
      bits[j+1]+=y;
      bits[j]-=(2*y);
    }
  }
  ll ans=1;
  for(int i=0;i<=61;i++){
    if(bits[i]==0){
      ll tot=1;
      for(int j=i-1;j>=0;j--){
        if(bits[j]==0){
	  break;
	}
	tot*=(ll)2;
      }
      ll rp=tot;
      ll p2=1;
      for(int j=i-1;j>=0;j--){
	if(bits[j]==0) break;
	p2*=(ll)2;
	if(bits[j]==2)
	  rp+=(tot/p2);
      }
      ans*=rp;
    }
  }
  //cout<<ans<<" "<<res<<endl;
  return ans;
}

Compilation message

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |       for(int j=0;j<a.size();j++) bits[j]=a[j];
      |                   ~^~~~~~~~~
biscuits.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i=0;i<a.size();i++)
      |               ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 54 ms 204 KB Output is correct
3 Correct 58 ms 272 KB Output is correct
4 Correct 71 ms 272 KB Output is correct
5 Correct 56 ms 276 KB Output is correct
6 Correct 63 ms 204 KB Output is correct
7 Correct 44 ms 204 KB Output is correct
8 Correct 61 ms 272 KB Output is correct
9 Correct 56 ms 284 KB Output is correct
10 Correct 43 ms 204 KB Output is correct
11 Correct 33 ms 204 KB Output is correct
12 Correct 99 ms 204 KB Output is correct
13 Correct 95 ms 204 KB Output is correct
14 Correct 84 ms 272 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 54 ms 204 KB Output is correct
3 Correct 58 ms 272 KB Output is correct
4 Correct 71 ms 272 KB Output is correct
5 Correct 56 ms 276 KB Output is correct
6 Correct 63 ms 204 KB Output is correct
7 Correct 44 ms 204 KB Output is correct
8 Correct 61 ms 272 KB Output is correct
9 Correct 56 ms 284 KB Output is correct
10 Correct 43 ms 204 KB Output is correct
11 Correct 33 ms 204 KB Output is correct
12 Correct 99 ms 204 KB Output is correct
13 Correct 95 ms 204 KB Output is correct
14 Correct 84 ms 272 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Incorrect 61 ms 272 KB Output isn't correct
25 Halted 0 ms 0 KB -