Submission #1159606
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<b;i++) //----------------------------------------------------------------- #define rrep(i,a,b) for(int i=a;i>=b;i--) vector<int> mul9(vector<int> s) { int n = s.size(), carry = 0; vector<int> ret; rrep(i, n - 1, 0) { int c = s[i] * 9 + carry; carry = c / 10; c %= 10; ret.push_back(c); } while (0 < carry) { ret.push_back(carry % 10); carry /= 10; } reverse(ret.begin(), ret.end()); return ret; } vector<int> add(vector<int> s, int x) { int n = s.size(), carry = x; vector<int> ret; rrep(i, n - 1, 0) { int c = s[i] + carry; carry = c / 10; c %= 10; ret.push_back(c); } while (0 < carry) { ret.push_back(carry % 10); carry /= 10; } reverse(ret.begin(), ret.end()); return ret; } //----------------------------------------------------------------- vector<int> N; bool chk(int k) { auto n = add(mul9(N), k); int cnt = 0; for (int c : n) cnt += c; return cnt <= k; } //----------------------------------------------------------------- int main() { string s; cin >> s; for (char c : s) N.push_back(c - '0'); int lo = 0, hi = 4501010; while (lo + 1 != hi) { int mi = (lo + hi) / 2; if (chk(mi)) hi = mi; else lo = mi; } int ans = hi / 9; if (hi % 9) ans++; cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - Increasing Numbers |
User | hamayanhamayan |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 1380 Byte |
Status | AC |
Exec Time | 159 ms |
Memory | 10956 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 1300 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All | sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in4.txt, in5.txt, in500000.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 4 ms | 564 KB |
in10.txt | AC | 151 ms | 10628 KB |
in11.txt | AC | 152 ms | 10660 KB |
in12.txt | AC | 151 ms | 10660 KB |
in13.txt | AC | 152 ms | 10660 KB |
in14.txt | AC | 151 ms | 10660 KB |
in15.txt | AC | 151 ms | 10660 KB |
in16.txt | AC | 136 ms | 10860 KB |
in17.txt | AC | 144 ms | 10208 KB |
in18.txt | AC | 152 ms | 10660 KB |
in19.txt | AC | 155 ms | 10472 KB |
in2.txt | AC | 151 ms | 10660 KB |
in20.txt | AC | 151 ms | 10660 KB |
in21.txt | AC | 152 ms | 10660 KB |
in22.txt | AC | 154 ms | 10660 KB |
in23.txt | AC | 159 ms | 10660 KB |
in24.txt | AC | 159 ms | 10660 KB |
in25.txt | AC | 151 ms | 10640 KB |
in26.txt | AC | 147 ms | 10380 KB |
in27.txt | AC | 103 ms | 9592 KB |
in28.txt | AC | 158 ms | 10624 KB |
in29.txt | AC | 153 ms | 10660 KB |
in3.txt | AC | 152 ms | 10628 KB |
in30.txt | AC | 159 ms | 10648 KB |
in31.txt | AC | 152 ms | 10660 KB |
in4.txt | AC | 159 ms | 10660 KB |
in5.txt | AC | 141 ms | 10936 KB |
in500000.txt | AC | 137 ms | 10956 KB |
in6.txt | AC | 151 ms | 10660 KB |
in7.txt | AC | 130 ms | 8996 KB |
in8.txt | AC | 150 ms | 10532 KB |
in9.txt | AC | 152 ms | 10660 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |
sample4.txt | AC | 1 ms | 256 KB |