Submission #1501774
Source Code Expand
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cctype> #include<cstdlib> #include<algorithm> #include<bitset> #include<vector> #include<list> #include<deque> #include<queue> #include<map> #include<set> #include<stack> #include<cmath> #include<sstream> #include<fstream> #include<iomanip> #include<ctime> #include<complex> #include<functional> #include<climits> #include<cassert> #include<iterator> #include<unordered_set> #include<unordered_map> using namespace std; #define MAX 500002 string s; char buf[MAX]; vector<string> add; string pluss(string a, string b, bool flag = false) { if (!flag) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); } if (a.size() > b.size()) { swap(a, b); } string ans; ans.clear(); long long int want = 0; for (int i = 0; i < a.size(); i++) { long long int val = a[i] - '0'; val += b[i] - '0'; val += want; want = val / 10LL; val %= 10LL; ans.push_back(val + '0'); } for (int j = a.size(); j < b.size(); j++) { long long int val = 0; val += b[j] - '0'; val += want; want = val / 10LL; val %= 10LL; ans.push_back(val + '0'); } while (want) { ans.push_back(want % 10 + '0'); want /= 10; } if (!flag) { reverse(ans.begin(), ans.end()); } if (ans.size() == 0)ans = "0"; return ans; } string mult(string a, string b, bool flag = false) { if (!flag) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); } string ans = "0"; string pas; string kari; pas.clear(); for (int i = 0; i < b.size(); i++) { long long int bb = b[i] - '0'; long long int tmp = 0; kari = pas; for (int j = 0; j < a.size(); j++) { long long int val = (long long int)(a[j] - '0')*bb; val += tmp; tmp = val / 10LL; val %= 10LL; kari.push_back(val + '0'); } while (tmp) { kari.push_back((tmp % 10LL) + '0'); tmp /= 10LL; } ans = pluss(ans, kari, true); //end pas.push_back('0'); } if (!flag) { reverse(ans.begin(), ans.end()); } if (ans.size() == 0)ans = "0"; return ans; } string minuss(string a, string b) { reverse(b.begin(), b.end()); reverse(a.begin(), a.end()); while (a.size()>b.size()) { b.push_back('0'); } while (a.size()<b.size()) { a.push_back('0'); } bool carry = false; for (int i = 0; i<a.size(); i++) { if (a[i] != '0'&&carry) { a[i]--; carry = false; } if (a[i] == '0'&&carry) { a[i] = '9'; } if (a[i] >= b[i]) { a[i] = (a[i] - '0') - (b[i] - '0') + '0'; } else { a[i] = (10 + (a[i] - '0') - (b[i] - '0')) + '0'; carry = true; } } while (a.size()>1 && a.back() == '0') { a.pop_back(); } reverse(a.begin(), a.end()); return a; } struct nex_list { set<pair<int, int> > s; void ins(int val) { s.insert(make_pair(val, val)); } void er(int val) { auto it = s.upper_bound(make_pair(val, INT_MAX)); it--; int lef = (*it).first; int rig = (*it).second; s.erase(it); if (lef < val) { s.insert(make_pair(lef, val - 1)); } if (val < rig) { s.insert(make_pair(val + 1, rig)); } } int get_end(int id) { auto it = s.upper_bound(make_pair(id, INT_MAX)); it--; id = (*it).first; int R = id; while (it != s.end()) { if ((*it).first <= R && (*it).second >= R) { R = (*it).second + 1; it = s.erase(it); } else { break; } } s.insert(make_pair(id, R-1)); return R - 1; } }; nex_list nx[10]; int main() { scanf("%s", buf); s = buf; int i = 0; int ans = 0; for (int i = 0; i < s.size(); i++) { nx[s[i] - '0'].ins(i); } while (i < s.size()) { if (s[i] == '0') { i++; continue; } //string f; int pr = -1; int il = i; int ir = nx[s[i] - '0'].get_end(il); while (ir + 1 < s.size() && s[ir] < s[ir+1]) { il = ir + 1; ir = nx[s[ir + 1]-'0'].get_end(ir + 1); } if (ir+1 != s.size()) { i = il + 1; } else { i = ir + 1; } ans++; if (i == s.size()) { break; } int carry = 1; for (int j = s.size() - 1; j >= i; j--) { nx[s[j] - '0'].er(j); carry += s[j] - '0'; s[j] = carry % 10; s[j] += '0'; nx[s[j] - '0'].ins(j); carry /= 10; if (carry == 0) { break; } } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Increasing Numbers |
User | Kmcode |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 4375 Byte |
Status | AC |
Exec Time | 400 ms |
Memory | 24832 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:176:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s", buf); ^
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 | 5 ms | 768 KB |
in10.txt | AC | 244 ms | 24576 KB |
in11.txt | AC | 170 ms | 24704 KB |
in12.txt | AC | 331 ms | 24704 KB |
in13.txt | AC | 294 ms | 24704 KB |
in14.txt | AC | 264 ms | 24704 KB |
in15.txt | AC | 239 ms | 24704 KB |
in16.txt | AC | 212 ms | 24704 KB |
in17.txt | AC | 92 ms | 23296 KB |
in18.txt | AC | 381 ms | 24704 KB |
in19.txt | AC | 314 ms | 24064 KB |
in2.txt | AC | 382 ms | 24704 KB |
in20.txt | AC | 93 ms | 24704 KB |
in21.txt | AC | 377 ms | 24704 KB |
in22.txt | AC | 375 ms | 24832 KB |
in23.txt | AC | 375 ms | 24704 KB |
in24.txt | AC | 249 ms | 24704 KB |
in25.txt | AC | 249 ms | 24576 KB |
in26.txt | AC | 358 ms | 23808 KB |
in27.txt | AC | 245 ms | 17408 KB |
in28.txt | AC | 380 ms | 24576 KB |
in29.txt | AC | 375 ms | 24704 KB |
in3.txt | AC | 376 ms | 24576 KB |
in30.txt | AC | 381 ms | 24704 KB |
in31.txt | AC | 373 ms | 24704 KB |
in4.txt | AC | 393 ms | 24704 KB |
in5.txt | AC | 82 ms | 24576 KB |
in500000.txt | AC | 165 ms | 24704 KB |
in6.txt | AC | 400 ms | 24704 KB |
in7.txt | AC | 262 ms | 19840 KB |
in8.txt | AC | 94 ms | 24320 KB |
in9.txt | AC | 253 ms | 24704 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 |