Submission #1870713
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))
#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;
VI all;
bool isInc(int x)
{
int last = 9;
while(x)
{
int cur = x % 10;
if (cur > last) return false;
last = cur;
x /= 10;
}
return true;
}
int greedy(int x)
{
if (x == 0) return 0;
int pos = upper_bound(ALL(all), x) - all.begin() - 1;
return greedy(x-all[pos]) + 1;
}
const int MAX = 10000000;
int DP[MAX];
void add(vector<PII>& a, int ind)
{
RFOR(i, SZ(a), ind - 1)
{
//cout<<"!! "<<i<<' '<<ind<<' '<<(char)a[i].first<<endl;
if (a[i].first == '9') a[i].first = '0';
else
{
//cout<<"^"<<endl;
if (a[i].second == 1) a[i].first++;
else
{
a[i].second--;
a.insert(a.begin() + i + 1, MP(a[i].first + 1, 1));
}
//cout<<"!!!!!!!!!!!!!!!!! "<<(char)a[i].first<<' '<<a[i].second<<endl;
break;
}
}
}
int NXT[MAX];
int PREV[MAX];
int get(string s)
{
vector<PII> a;
a.PB(MP(s[0], 0));
FOR (i, 0, SZ(s))
{
if (a.back().first != s[i]) a.PB(MP(s[i], 0));
a.back().second++;
}
int ind = 0;
int res = 0;
int iter = 0;
while(true)
{
/* FOR (i, ind, SZ(a))
{
cout<<"("<<(char)a[i].first<<' '<<a[i].second<<") ";
}
cout<<endl;
iter++;
if (iter % 1000 == 0)
{
cout<<ind<<' '<<SZ(a)<<' '<<a[ind].second<<endl;
}*/
// cout<<ind<<' '<<SZ(s)<<endl;
int prev = ind;
string cur = "";
while(ind < SZ(a) - 1)
{
if (a[ind].first <= a[ind+1].first)
{
ind++;
}
else break;
}
if (ind != SZ(a) - 1)
{
while(ind > prev && a[ind].first == a[ind-1].first)
{
ind--;
}
}
// FOR (i, prev, ind) cur += s[i];
// cur += s[ind] - 1;
// FOR (i, ind+1, SZ(s)) cur += '9';
//cout<<cur<<endl;
a[ind].second--;
//cout<<"!! "<<a[ind].second<<endl;
res++;
if (ind == SZ(a) - 1) break;
if (a[ind].second == 0) ind++;
add(a, ind);
if (ind >= SZ(a)) break;
}
return res;
}
string str(int x)
{
string res;
while(x)
{
res += x % 10 + '0';
x /= 10;
}
reverse(ALL(res));
return res;
}
int main()
{
//freopen("in.txt", "r", stdin);
//ios::sync_with_stdio(false); cin.tie(0);
//cout<<get("11")<<endl;
//return 0;
/* FOR (i, 0, MAX)
{
if (isInc(i)) all.PB(i);
}
cout<<SZ(all)<<endl;
FOR (i, 1, MAX)
{
int v1 = greedy(i);
int v2 = get(str(i));
cout<<i<<' '<<v1<<' '<<v2<<endl;
if (v1 != v2)
{
cout<<"!! "<<i<<endl;
cout<<v1<<' '<<v2<<endl;
throw -1;
}
}
cout<<"OK"<<endl;
return 0;*/
string s;
cin>>s;
//s = string(100000, '9');
//s += string(1000000, '0');
cout<<get(s)<<endl;
/* FOR (i, 0, MAX)
{
if (isInc(i)) all.PB(i);
}
cout<<SZ(all)<<endl;
DP[0] = 0;
FOR (i, 1, MAX)
{
if (i % 10000 == 0) cout<<i<<endl;
DP[i] = INF;
FOR (j, 0, SZ(all))
{
if (all[j] > i) break;
DP[i] = min(DP[i], DP[i-all[j]] + 1);
}
if (DP[i] != greedy(i))
{
cout<<"!! "<<i<<endl;
cout<<DP[i]<<' '<<greedy(i)<<endl;
throw -1;
}
}*/
}
Submission Info
Submission Time |
|
Task |
E - Increasing Numbers |
User |
vjudge5 |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
3406 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
7544 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 |
2 ms |
512 KB |
in10.txt |
AC |
27 ms |
1412 KB |
in11.txt |
AC |
18 ms |
1412 KB |
in12.txt |
AC |
19 ms |
1412 KB |
in13.txt |
AC |
25 ms |
1412 KB |
in14.txt |
AC |
26 ms |
1412 KB |
in15.txt |
AC |
27 ms |
1412 KB |
in16.txt |
AC |
27 ms |
1412 KB |
in17.txt |
AC |
17 ms |
1284 KB |
in18.txt |
AC |
30 ms |
6136 KB |
in19.txt |
AC |
27 ms |
6136 KB |
in2.txt |
AC |
30 ms |
6904 KB |
in20.txt |
AC |
18 ms |
1412 KB |
in21.txt |
AC |
30 ms |
6776 KB |
in22.txt |
AC |
30 ms |
5752 KB |
in23.txt |
AC |
30 ms |
5880 KB |
in24.txt |
AC |
26 ms |
1412 KB |
in25.txt |
AC |
26 ms |
1412 KB |
in26.txt |
AC |
29 ms |
7416 KB |
in27.txt |
AC |
22 ms |
6904 KB |
in28.txt |
AC |
30 ms |
7416 KB |
in29.txt |
AC |
30 ms |
7544 KB |
in3.txt |
AC |
30 ms |
5752 KB |
in30.txt |
AC |
30 ms |
7032 KB |
in31.txt |
AC |
30 ms |
7032 KB |
in4.txt |
AC |
30 ms |
5880 KB |
in5.txt |
AC |
18 ms |
1412 KB |
in500000.txt |
AC |
18 ms |
1412 KB |
in6.txt |
AC |
31 ms |
6136 KB |
in7.txt |
AC |
23 ms |
5496 KB |
in8.txt |
AC |
18 ms |
1284 KB |
in9.txt |
AC |
27 ms |
1412 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 |