Cod sursa(job #2222746)
| Utilizator |  Marius B mgnt |
Data | 17 iulie 2018 23:04:15 |
|---|---|---|---|
| Problema | Grupuri | Scor | 64 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 38.39 kb |
#include <cstddef>
#include <limits>
#include <vector>
#include <fstream>
#include <iostream>
bool
demo
()
{
#define FOLD_DEMO_STATE
#ifdef FOLD_DEMO_STATE
/// stsz : simple type size
/// stuw : simple type unsigned word
/// vtuw : vector type unsigned word
/// stud : simple type unsigned double word
typedef ::std::size_t stsz;
typedef unsigned stuw;
typedef ::std::vector < stuw > vtuw;
typedef unsigned long long stud;
/// problem size constants
stsz const min_k = 1;
stsz const max_n = 100000;
stuw const min_a = 0;
stuw const max_a = 1000000;
/// risk : [r]aw [i]nput [s]calar k
/// risn : [r]aw [i]nput [s]calar n
/// riva : [r]aw [i]nput [v]ector a
stsz risk = 0;
stsz risn = 0;
vtuw riva;
/// srvp : [s]tai[r]s [v]ector [p]airs
/// srpb : [s]tai[r]s [p]refix [b]order
/// srsb : [s]tai[r]s [s]uffix [b]order
/// srpr : [s]tai[r]s [p]refix [r]eminder
/// srsa : [s]tai[r]s [s]uffix [f]all
/// srsp : [s]tai[r]s [s]uffix s[p]an
vtuw srvp;
stsz srpb = 0;
stsz srsb = 0;
stuw srpr = 0;
stuw srsf = 0;
stuw srsp = 0;
/// nogr : number of groups
stud nogr = 0;
#define MEMO_stsz__simple_type_size
#define MEMO_stuw__simple_type_unsigned_word
#define MEMO_stuw__vector_type_unsigned_word
#define MEMO_imza__intermezzo_a__________
#define MEMO_risk__raw_input_scalar_k
#define MEMO_risn__raw_input_scalar_n
#define MEMO_riva__raw_input_vector_a
#define MEMO_imza__intermezzo_b__________
#define MEMO_srvp__stairs_vector_pairs
#define MEMO_srpb__stairs_prefix_border
#define MEMO_srsb__stairs_suffix_border
#define MEMO_srpr__stairs_prefix_reminder
#define MEMO_srsf__stairs_suffix_fall
#define MEMO_srsp__stairs_suffix_span
#define MEMO_imza__intermezzo_c__________
#define MEMO_nogr__number_of_groups
#endif
if (true) { /// test
/// Test implementation limits.
stsz const max_sz = :: std :: numeric_limits < stsz > :: max ( );
bool ok = false;
ok = ( (max_n <= max_sz)
&& (max_n <= (max_sz - max_n) )
);
if ( ! ok )
{
/// Implementation limits.
::std::cerr << "E1" << ::std::endl;
return false;
}
stuw const max_uw = :: std :: numeric_limits < stuw > :: max ( );
ok = (max_n <= max_uw);
if ( ! ok )
{
/// Implementation limits.
::std::cerr << "E2" << ::std::endl;
return false;
}
}
if (true) { /// read
/// Read input.
stsz tk;
stsz tn;
::std::ifstream is("grupuri.in");
is >> tk >> tn;
vtuw ta(tn);
::std::size_t i;
for ( i = 0; tn > i; ++i )
{
stuw & ai = ta[i];
is >> ai;
}
risk = tk;
risn = tn;
riva.swap(ta);
}
if (true) { /// test
/// Validate input.
bool ok = false;
ok = ( (min_k <= risk)
&& (risk <= risn)
&& (risn <= max_n)
);
if ( !ok)
{
ok = true;
}
if ( !ok )
{
/// Invalid input.
::std::cerr << "E3" << ::std::endl;
return false;
}
stuw b = min_a;
stsz i = 0;
stuw d = 0;
for ( i = 0; risn > i; ++ i )
{
d = riva[i];
ok = (b <= d);
if ( !ok )
{
/// Invalid input.
::std::cerr << "E4" << ::std::endl;
return false;
}
b = d;
}
ok = (d <= max_a);
if ( !ok)
{
ok = true;
}
if ( !ok )
{
/// Invalid input.
::std::cerr << "E5" << ::std::endl;
return false;
}
}
if (true) { /// count
/// Count stairs.
stsz m = 0;
stuw h = riva[0];
stsz i = 0;
stuw v = 0;
for ( i = 1; risn > i; ++ i )
{
v = riva[i];
if ( v != h )
{
if ( 0 < h )
{
++m;
}
h = v;
}
}
if (0 < h)
{
++m;
}
if (0 < m)
{
stsz const w = m + m;
vtuw txvp(w);
srvp.swap(txvp);
}
}
if (true) { /// amass
/// Amass raw input into stairs.
stsz m = 0;
stuw h = riva[0];
stsz s = 1;
stsz i = 0;
stuw v = 0;
stuw t = 0;
for ( i = 1; risn > i; ++ i )
{
v = riva[i];
if ( h == v )
{
++ s;
}
else
{
if ( 0 < h )
{
t = static_cast < stuw > (s);
srvp[m] = h;
++ m;
srvp[m] = t;
++ m;
}
h = v;
s = 1;
}
}
if ( 0 < h )
{
t = static_cast < stuw > (s);
srvp[m] = h;
++ m;
srvp[m] = t;
++ m;
}
}
if (true) { /// split
/// Split stairs into prefix and suffix.
stsz i = srvp.size();
stsz j = i;
stuw s = 0;
stuw h = 0;
stuw u = 0;
stuw w = 0;
stuw r = 0;
while ( 0 < i )
{
-- i;
s = srvp[i];
-- i;
h = srvp[i];
(void) h;
w = u + s;
if ( risk <= w )
{
break;
}
u = w;
j = i;
}
if ( 0 < j )
{
r = srvp[j-1];
}
srpb = j;
srsb = j;
srpr = r;
srsf = 0;
srsp = u;
}
if (true) { /// count
/// Count groups.
while (2 <= srpb)
{
#define FOLD_COUNT_ROUND_STATE
#ifdef FOLD_COUNT_ROUND_STATE
stuw const q = risk - srsp;
stuw const y = (4 <= srpb) ? srvp[srpb - 4] : 0;
stuw a = srvp[srpb - 2] - y;
stuw b = srpr;
stuw const c = srvp[srpb - 1];
stuw const v = (0 < srsp) ? ((srvp[srsb + 0] - srsf) - y) : 0;
stuw d = v;
stuw t = 0;
stuw s = 0;
stuw z = 0;
stuw const g = nogr;
#endif
if (true) { /// dig
while ( ( (1 < a) || ( (1 == a) && (q <= b) ) )
&& ( (0 == srsp) || (a < d) )
)
{
if (q <= b)
{
t = b / q;
if (0 < srsp)
{
s = d - a;
t = (s < t) ? s : t;
d = d - t;
}
nogr = nogr + t;
b = b - t * q;
if (0 == b)
{
a = a - 1;
b = c;
}
}
else
{
if (0 < srsp)
{
d = d - 1;
}
nogr = 1 + nogr;
a = a - 1;
b = c - (q - b);
}
}
}
if (true) { /// 321
if (g < nogr)
{
if (true) { /// 32
if (0 < srsp)
{
srsf = srsf + (v - d);
if (a == d)
{
z = srvp[1 + srsb];
srsp = srsp - z;
srsb = 2 + srsb;
}
}
}
if (true) { /// 21
if ( (4 > srpb) || (1 < a) )
{
srvp[srpb - 2] = y + a;
srvp[srpb - 1] = c + z;
srpr = b + z;
if ( (0 == y) && (0 == a) )
{
srpb = srpb - 2;
}
}
else
{
srpb = srpb - 2;
srvp[srpb - 2] = y + a;
srvp[srpb - 1] = srvp[srpb - 1] + (c + z);
srpr = (1 == a) ? (b + z) : srvp[srpb - 1];
}
}
}
else
{
srpb = 0;
}
}
}
}
if (true) { /// write
/// Write solution.
::std::ofstream os("grupuri.out");
os << nogr << "\n";
}
return true;
}
int
main
()
{
int status;
try
{
bool const ok = demo();
status = ( ok ? 0 : 1 );
}
catch ( ... )
{
try
{
::std::cerr << "E6" << ::std::endl;
}
catch ( ... )
{
}
status = 2;
}
return status;
}
