Submission #991884
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) #define thd(t) std::get<2>(t) using ll = long long; using P = std::tuple<int,int>; const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1}; std::vector<int> v; ll N; bool can(ll x){ v.clear(); int rest = N; for(int i=x;i>0;--i){ if(rest >= i){ v.emplace_back(i); rest -= i; } } // std::cout << x << ": " << rest << std::endl; return rest == 0; } int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cin >> N; // if minimizing, lb satisfies lb > ub // if maximizing, lb satisfies lb < ub ll lb = N, ub = 0; while(std::abs(ub - lb) > 1){ ll mid = (lb + ub) / 2; if(can(mid)){ // std::cout << "ok: " << mid << std::endl; lb = mid; }else{ // std::cout << "ng: " << mid << std::endl; ub = mid; } } // std::cout << lb << std::endl; can(lb); for(int x : v){ std::cout << x << std::endl; } }
Submission Info
Submission Time | |
---|---|
Task | B - Exactly N points |
User | iwashisnake |
Language | C++14 (GCC 5.4.1) |
Score | 300 |
Code Size | 1233 Byte |
Status | AC |
Exec Time | 41 ms |
Memory | 384 KB |
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 100 / 100 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
dataset1 | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
dataset2 | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 2 ms | 256 KB |
01-02.txt | AC | 2 ms | 256 KB |
01-03.txt | AC | 3 ms | 256 KB |
01-04.txt | AC | 3 ms | 256 KB |
01-05.txt | AC | 3 ms | 256 KB |
01-06.txt | AC | 3 ms | 256 KB |
01-07.txt | AC | 3 ms | 256 KB |
01-08.txt | AC | 3 ms | 256 KB |
01-09.txt | AC | 3 ms | 256 KB |
01-10.txt | AC | 3 ms | 256 KB |
02-01.txt | AC | 41 ms | 384 KB |
02-02.txt | AC | 41 ms | 384 KB |
02-03.txt | AC | 40 ms | 384 KB |
02-04.txt | AC | 41 ms | 384 KB |
02-05.txt | AC | 40 ms | 384 KB |
02-06.txt | AC | 18 ms | 256 KB |
02-07.txt | AC | 12 ms | 256 KB |
02-08.txt | AC | 39 ms | 384 KB |
sample-01.txt | AC | 3 ms | 256 KB |
sample-02.txt | AC | 3 ms | 256 KB |
sample-03.txt | AC | 3 ms | 256 KB |