oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

potatoguard Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Problem Description.html

Problem Description

There are n bushes in a row conveniently labelled 1 to n in IOI Kingdom, each of them can either contain a ninja (or not). Also, potato knows that there are k ninjas in these n bushes.

Potato wants to invade IOI kingdom and get some gold. He may call upon some royal potato guards one by one to check out the bushes. Potato can command a royal potato guard to count the number of ninjas in a range starting from bush 1, then the next guard, until he can decide the positions of the ninjas.

Potato wants to minimize the number of royal potato guards he needs to call upon to guarantee that he can find the ninjas. However, potato realizes this is a non-trivial problem! He asks you for help in order to reduce the number of royal guards he needs to command.

Your Task

void Potate(int n, int k) will be called. n, k indicates the number of bushes and ninjas respectively. This function should find the position of all ninjas.

Interaction

You may use the following functions:

  • int Guard(int x): returns the number of ninjas in bushes 1 to x inclusive.
  • void Ninja(int x): indicates that there is a ninja at bush x. You have to call this function exactly once for each ninja.

Subtasks

Subtask 1 (16 points): 1 ≤ k ≤ n ≤ 30

Subtask 2 (22 points): 1 ≤ k ≤ n ≤ 90

Subtask 3 (42 points): 1 ≤ k ≤ n ≤ 400

Subtask 4 (20 points): 1 ≤ k ≤ 50000, n ≤ 1000000000, 1 ≤ k ≤ n

Tags

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1161000.5s64MBMinimum
2222000.5s64MBMinimum
3422500.5s64MBMinimum
4203000.5s64MBMinimum

Attachments

Attachment Filesize Last Updated
potatoguard.h64B30 Jun 2018, 20:37:49
grader.cpp493B30 Jun 2018, 20:37:49
ans.cpp123B30 Jun 2018, 20:37:49

Judge Compile Command

g++-8 ans.cpp grader.cpp -o potatoguard -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.