Submission #1291954


Source Code Expand

#include <iostream>
#include"grader.h"
using namespace std;
typedef long long ll;
 
 
ll memo[51][20000];
ll calc(int nMiss, int nTotal) {
  if(nMiss > nTotal) return calc(nTotal, nTotal);
  if(nMiss == 0) return 1;
  if(nMiss == 1) return nTotal + 1;
  if(nMiss == 2) return nTotal * ll(nTotal+1) / 2;
  ll& res = memo[nMiss][nTotal];
  if(res == 0){
    res = calc(nMiss-1, nTotal-1) + calc(nMiss, nTotal-1);
  }
  return res;
}
 
long long getT(int N, long long M) {
  
  for(int i = 0; i <= 50; i++)memo[i][0]=1;
  int nTotal = 1;
  for(; nTotal < 20000; nTotal++){
    memo[0][nTotal]=1;
    memo[1][nTotal]=nTotal+1;
    memo[2][nTotal]=nTotal * ll(nTotal+1) / 2;
    for(int i = 3; i <= N; i++){
      memo[i][nTotal]=memo[i-1][nTotal-1]+memo[min(i,nTotal-1)][nTotal-1];
    }
    if(M+1 <= memo[min(N,nTotal)][nTotal])break;
  }
  
  //while(calc(N, nTotal) < M+1){
  //  ++nTotal;
  //}
  
  ll mini = 0;
  ll maxi = M;
  while(mini < maxi){
    ll X = min(mini + memo[min(N-1,nTotal-1)][nTotal-1]/*calc(N-1, nTotal-1)*/-1, maxi);
    if(compare(X)){ // T <= X
      --N;
      maxi = X;
    }else{
      mini = X+1;
    }
    --nTotal;
  }
  return mini;
}

Submission Info

Submission Time
Task C - 提出 (Submission)
User eukaryo
Language IOI-Style C++ (GCC 5.4.1)
Score 75
Code Size 1216 Byte
Status TLE
Exec Time 5255 ms
Memory 5212 KB

Compile Error

./grader.cpp: In function ‘int compare(long long int)’:
./grader.cpp:20:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int result; scanf("%d", &result);
                                   ^
./grader.cpp: In function ‘int main()’:
./grader.cpp:32:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld", &inN, &M);
                            ^

Judge Result

Set Name Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 25 25 / 25 50 / 50
Status
AC × 5
TLE × 5
AC × 10
AC × 10
Set Name Test Cases
Subtask1 subtask1/1, subtask1/10, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9
Subtask2 subtask2/1, subtask2/10, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask2/7, subtask2/8, subtask2/9
Subtask3 subtask3/1, subtask3/10, subtask3/2, subtask3/3, subtask3/4, subtask3/5, subtask3/6, subtask3/7, subtask3/8, subtask3/9
Case Name Status Exec Time Memory
subtask1/1 AC 4 ms 5208 KB
subtask1/10 TLE 5255 ms 5212 KB
subtask1/2 AC 3 ms 5212 KB
subtask1/3 AC 3 ms 5204 KB
subtask1/4 AC 3 ms 5212 KB
subtask1/5 TLE 5255 ms 5212 KB
subtask1/6 TLE 5255 ms 5212 KB
subtask1/7 AC 221 ms 4824 KB
subtask1/8 TLE 5255 ms 5208 KB
subtask1/9 TLE 5255 ms 5208 KB
subtask2/1 AC 3 ms 4700 KB
subtask2/10 AC 34 ms 4692 KB
subtask2/2 AC 3 ms 4696 KB
subtask2/3 AC 27 ms 4700 KB
subtask2/4 AC 3 ms 4700 KB
subtask2/5 AC 3 ms 4700 KB
subtask2/6 AC 19 ms 4696 KB
subtask2/7 AC 35 ms 4700 KB
subtask2/8 AC 38 ms 4696 KB
subtask2/9 AC 3 ms 4700 KB
subtask3/1 AC 4 ms 4696 KB
subtask3/10 AC 4 ms 4700 KB
subtask3/2 AC 4 ms 4696 KB
subtask3/3 AC 4 ms 4696 KB
subtask3/4 AC 3 ms 4700 KB
subtask3/5 AC 4 ms 4696 KB
subtask3/6 AC 4 ms 4696 KB
subtask3/7 AC 4 ms 4696 KB
subtask3/8 AC 4 ms 4696 KB
subtask3/9 AC 4 ms 4700 KB