oj.uz

Submission #20614

# Submission time Handle Problem Language Result Execution time Memory
20614 2017-02-12T16:38:28 Z model_code Aliens (IOI16_aliens) C++11
100 / 100
 159 ms 44788 KB 
// name = alien-bsearch.cpp, type = cpp.g++11

#include "aliens.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define MAXN 1000001
#define pb push_back
#define INFI (~(1LL<<63))
#define sq(x) ((x) * (x))
#define DELTA 0.000001

struct range{
 ll s, e;
 friend bool operator < (const range &a, const range &b) {
  if (a.s == b.s)
   return (a.e > b.e) ? true : false;
  else
   return (a.s < b.s) ? true : false;
  }
};


struct point {
 ll x, y;
};

struct line {
 ll m, c;
};

struct hull_line {
 ll m, c;
 ll k;
};

class Hull {
private:
 int cur, len;
 hull_line *L;
 double getx(ll m1, ll c1, ll m2, ll c2);

public:
 void addline(ll m, ll c, ll k);
 pair<ll,ll> getmin(ll x);
 void resetline();
 Hull();
 ~Hull();
};

Hull::Hull() {
 L = (hull_line*)malloc(MAXN * sizeof(hull_line));
}

Hull::~Hull() {
 free(L);
}

double Hull::getx(ll m1, ll c1, ll m2, ll c2) {
 return (c2-c1) / (double)(m1-m2);
}

void Hull::addline(ll m, ll c, ll k) {
 while (len >= 2) {
  double a = getx(m, c, L[len-1].m, L[len-1].c);
  double b = getx(m, c, L[len-2].m, L[len-2].c);
  if (a > b) break;
  len--;
 }
 L[len].m = m;
 L[len].c = c;
 L[len].k = k;
 len++;
}

pair<ll,ll> Hull::getmin(ll x) {
 if (cur >= len) cur = len-1;
 while (cur < len-1) {
  double a = getx(L[cur].m, L[cur].c, L[cur+1].m, L[cur+1].c);
  if (x > a)
   cur++;
  else
   break;
   // in case x==a first such line is considered
   // It can be proven using convex property
   // that k increase as cur increases
 }
 return make_pair(L[cur].m * x + L[cur].c, L[cur].k);
}

void Hull::resetline() {
 len = 0;
 cur = 0;
}


pair<ll,ll> hull(vector<range> &r, ll C, Hull &h) {
 int n = r.size();
 ll m, c;
 ll t, lastRes = 0LL, lastK = 0LL;
 h.resetline();
 pair<ll,ll> res;
 for (int i=0; i<n; ++i) {
  m = -2LL * (r[i].s - 1LL);
  c = lastRes + sq(r[i].s - 1LL);
  if (i > 0) {
   t = max(0LL, r[i-1].e - r[i].s + 1LL);
   c -= sq(t);
  }
  h.addline(m, c, lastK);
  res = h.getmin(r[i].e);
  lastRes = sq(r[i].e) + C + res.first;
  lastK = res.second + 1LL;
 }
 return make_pair(lastRes, lastK);;
}

ll find(vector<range> &r, int K, int M) {
 Hull h;
 int N = r.size();
 K = min(K, N);
 ll kl=1LL, kr=(ll)N, cl = sq((ll)M), cr=0LL;
 ll med;
 bool found = false;
 pair<ll,ll> res;
 if (cl % 2LL == 1LL) cl++; // keep C left to an even integer
 // run binary search on C=[cl,cr]
 while (kr-kl > 1LL && cl - cr > 1LL) {
  med = cr + (cl-cr)/2LL;
  // if (med % 2LL == 1LL) med--; // keep med even
  res = hull(r, med + 1LL, h);
  if (K == res.second) {
   found = true;
   break;
  }
  if (K < res.second) {
   cr = med;
   kr = res.second;
  } else {
   cl = med;
   kl = res.second;
  }
 }
 if (found) {
  return res.first - (med+1LL) * K;
 } else if (kr - kl > 1) {
  // slope is equal from kl to kr.
  // Since odd C values are used in hull() it always returns
  // leftmost k out of those slopes for given C. i.e. slopes are always even
  res = hull(r, cl+1LL, h);
  ll fl = res.first - (cl + 1LL) * kl;
  res = hull(r, cr+1LL, h);
  ll fr = res.first - (cr + 1LL) * kr;
  ll h = (fl-fr) / (kr - kl); // interpolate
  return fl - (K - kl) * h;
 } else {
  if (kr == K) {
   res = hull(r, cr + 1LL, h);
   return res.first - (cr + 1LL) * K;
  } else { //kr = K
   res = hull(r, cl + 1LL, h);
   return res.first - (cl + 1LL) * kl;
  }
 }
}

vector<range> parseRanges(range* r, int n) {
 sort(&r[0], &r[n]);
 vector<range> res;
 int cur = 0;
 res.pb(r[0]);
 for (int i=1; i<n; ++i)
  if (r[cur].e < r[i].s || r[cur].e < r[i].e) {
   cur = i;
   res.pb(r[i]);
  }
 return res;
}

long long take_photos(int n, int m, int k, vector<int> row, vector<int> col) {
 point *p = (point*)malloc(MAXN * sizeof(point));
 range *r = (range*)malloc(MAXN * sizeof(range));
 for (int i=0; i<n; ++i) {
  r[i].s = min(row[i], col[i]);
  r[i].e = max(row[i], col[i]);
 }
 vector<range> R = parseRanges(r, n);
 ll res = find(R, k, m);

 // do the same for other diagonal
 // for (int i=0; i<n; ++i) {
 //  r[i].s = min(p[i].y,m-p[i].x-1);
 //  r[i].e = max(p[i].y,m-p[i].x-1);
 // }
 // R = parseRanges(r, n);
 //res = min(res, find(R, k, m));
 return res;
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:185:9: warning: unused variable 'p' [-Wunused-variable]
  point *p = (point*)malloc(MAXN * sizeof(point));
         ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41092 KB Correct answer: answer = 4
2 Correct 0 ms 41092 KB Correct answer: answer = 4
3 Correct 0 ms 41092 KB Correct answer: answer = 4
4 Correct 0 ms 41092 KB Correct answer: answer = 12
5 Correct 0 ms 41092 KB Correct answer: answer = 52
6 Correct 0 ms 41092 KB Correct answer: answer = 210
7 Correct 0 ms 41092 KB Correct answer: answer = 88
8 Correct 0 ms 41092 KB Correct answer: answer = 7696
9 Correct 0 ms 41092 KB Correct answer: answer = 1
10 Correct 0 ms 41092 KB Correct answer: answer = 2374
11 Correct 0 ms 41092 KB Correct answer: answer = 9502
12 Correct 0 ms 41092 KB Correct answer: answer = 49
13 Correct 0 ms 41092 KB Correct answer: answer = 151
14 Correct 0 ms 41092 KB Correct answer: answer = 7550
15 Correct 0 ms 41092 KB Correct answer: answer = 7220
16 Correct 0 ms 41092 KB Correct answer: answer = 7550
17 Correct 0 ms 41092 KB Correct answer: answer = 10000
18 Correct 0 ms 41092 KB Correct answer: answer = 10000
19 Correct 0 ms 41092 KB Correct answer: answer = 624
20 Correct 0 ms 41092 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41092 KB Correct answer: answer = 1
2 Correct 0 ms 41092 KB Correct answer: answer = 4
3 Correct 0 ms 41092 KB Correct answer: answer = 1
4 Correct 0 ms 41092 KB Correct answer: answer = 5
5 Correct 0 ms 41092 KB Correct answer: answer = 41
6 Correct 0 ms 41092 KB Correct answer: answer = 71923
7 Correct 0 ms 41092 KB Correct answer: answer = 77137
8 Correct 0 ms 41092 KB Correct answer: answer = 764
9 Correct 0 ms 41092 KB Correct answer: answer = 250000
10 Correct 0 ms 41092 KB Correct answer: answer = 500
11 Correct 0 ms 41092 KB Correct answer: answer = 32
12 Correct 0 ms 41092 KB Correct answer: answer = 130050
13 Correct 0 ms 41092 KB Correct answer: answer = 5110
14 Correct 0 ms 41092 KB Correct answer: answer = 2626
15 Correct 0 ms 41092 KB Correct answer: answer = 796
16 Correct 0 ms 41092 KB Correct answer: answer = 7580
17 Correct 0 ms 41092 KB Correct answer: answer = 1904
18 Correct 0 ms 41092 KB Correct answer: answer = 996004
19 Correct 0 ms 41092 KB Correct answer: answer = 38817
20 Correct 0 ms 41092 KB Correct answer: answer = 4096
21 Correct 0 ms 41092 KB Correct answer: answer = 1
22 Correct 0 ms 41092 KB Correct answer: answer = 1
23 Correct 0 ms 41092 KB Correct answer: answer = 2040
24 Correct 0 ms 41092 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41092 KB Correct answer: answer = 4
2 Correct 0 ms 41092 KB Correct answer: answer = 4
3 Correct 0 ms 41092 KB Correct answer: answer = 4
4 Correct 0 ms 41092 KB Correct answer: answer = 12
5 Correct 0 ms 41092 KB Correct answer: answer = 52
6 Correct 0 ms 41092 KB Correct answer: answer = 210
7 Correct 0 ms 41092 KB Correct answer: answer = 88
8 Correct 0 ms 41092 KB Correct answer: answer = 7696
9 Correct 0 ms 41092 KB Correct answer: answer = 1
10 Correct 0 ms 41092 KB Correct answer: answer = 2374
11 Correct 0 ms 41092 KB Correct answer: answer = 9502
12 Correct 0 ms 41092 KB Correct answer: answer = 49
13 Correct 0 ms 41092 KB Correct answer: answer = 151
14 Correct 0 ms 41092 KB Correct answer: answer = 7550
15 Correct 0 ms 41092 KB Correct answer: answer = 7220
16 Correct 0 ms 41092 KB Correct answer: answer = 7550
17 Correct 0 ms 41092 KB Correct answer: answer = 10000
18 Correct 0 ms 41092 KB Correct answer: answer = 10000
19 Correct 0 ms 41092 KB Correct answer: answer = 624
20 Correct 0 ms 41092 KB Correct answer: answer = 10000
21 Correct 0 ms 41092 KB Correct answer: answer = 1
22 Correct 0 ms 41092 KB Correct answer: answer = 4
23 Correct 0 ms 41092 KB Correct answer: answer = 1
24 Correct 0 ms 41092 KB Correct answer: answer = 5
25 Correct 0 ms 41092 KB Correct answer: answer = 41
26 Correct 0 ms 41092 KB Correct answer: answer = 71923
27 Correct 0 ms 41092 KB Correct answer: answer = 77137
28 Correct 0 ms 41092 KB Correct answer: answer = 764
29 Correct 0 ms 41092 KB Correct answer: answer = 250000
30 Correct 0 ms 41092 KB Correct answer: answer = 500
31 Correct 0 ms 41092 KB Correct answer: answer = 32
32 Correct 0 ms 41092 KB Correct answer: answer = 130050
33 Correct 0 ms 41092 KB Correct answer: answer = 5110
34 Correct 0 ms 41092 KB Correct answer: answer = 2626
35 Correct 0 ms 41092 KB Correct answer: answer = 796
36 Correct 0 ms 41092 KB Correct answer: answer = 7580
37 Correct 0 ms 41092 KB Correct answer: answer = 1904
38 Correct 0 ms 41092 KB Correct answer: answer = 996004
39 Correct 0 ms 41092 KB Correct answer: answer = 38817
40 Correct 0 ms 41092 KB Correct answer: answer = 4096
41 Correct 0 ms 41092 KB Correct answer: answer = 1
42 Correct 0 ms 41092 KB Correct answer: answer = 1
43 Correct 0 ms 41092 KB Correct answer: answer = 2040
44 Correct 0 ms 41092 KB Correct answer: answer = 2
45 Correct 0 ms 41092 KB Correct answer: answer = 4
46 Correct 0 ms 41092 KB Correct answer: answer = 9
47 Correct 0 ms 41092 KB Correct answer: answer = 9
48 Correct 0 ms 41092 KB Correct answer: answer = 21
49 Correct 0 ms 41092 KB Correct answer: answer = 71
50 Correct 0 ms 41092 KB Correct answer: answer = 77
51 Correct 0 ms 41092 KB Correct answer: answer = 400
52 Correct 0 ms 41092 KB Correct answer: answer = 996004
53 Correct 0 ms 41092 KB Correct answer: answer = 997310
54 Correct 0 ms 41092 KB Correct answer: answer = 990781
55 Correct 0 ms 41092 KB Correct answer: answer = 996545
56 Correct 0 ms 41092 KB Correct answer: answer = 484
57 Correct 0 ms 41092 KB Correct answer: answer = 484
58 Correct 0 ms 41092 KB Correct answer: answer = 63501
59 Correct 0 ms 41092 KB Correct answer: answer = 323501
60 Correct 0 ms 41092 KB Correct answer: answer = 752500
61 Correct 0 ms 41092 KB Correct answer: answer = 761480
62 Correct 0 ms 41092 KB Correct answer: answer = 758932
63 Correct 0 ms 41092 KB Correct answer: answer = 1000000
64 Correct 0 ms 41092 KB Correct answer: answer = 750500
65 Correct 0 ms 41092 KB Correct answer: answer = 1000000
66 Correct 0 ms 41092 KB Correct answer: answer = 250000
67 Correct 0 ms 41092 KB Correct answer: answer = 250000
68 Correct 0 ms 41092 KB Correct answer: answer = 1000000
69 Correct 0 ms 41092 KB Correct answer: answer = 994009
70 Correct 0 ms 41092 KB Correct answer: answer = 59315
71 Correct 0 ms 41092 KB Correct answer: answer = 25454
72 Correct 0 ms 41092 KB Correct answer: answer = 1504
73 Correct 0 ms 41092 KB Correct answer: answer = 37486
74 Correct 0 ms 41092 KB Correct answer: answer = 4284
75 Correct 0 ms 41092 KB Correct answer: answer = 158008
76 Correct 0 ms 41092 KB Correct answer: answer = 51860
77 Correct 0 ms 41092 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41092 KB Correct answer: answer = 4
2 Correct 0 ms 41092 KB Correct answer: answer = 4
3 Correct 0 ms 41092 KB Correct answer: answer = 4
4 Correct 0 ms 41092 KB Correct answer: answer = 12
5 Correct 0 ms 41092 KB Correct answer: answer = 52
6 Correct 0 ms 41092 KB Correct answer: answer = 210
7 Correct 0 ms 41092 KB Correct answer: answer = 88
8 Correct 0 ms 41092 KB Correct answer: answer = 7696
9 Correct 0 ms 41092 KB Correct answer: answer = 1
10 Correct 0 ms 41092 KB Correct answer: answer = 2374
11 Correct 0 ms 41092 KB Correct answer: answer = 9502
12 Correct 0 ms 41092 KB Correct answer: answer = 49
13 Correct 0 ms 41092 KB Correct answer: answer = 151
14 Correct 0 ms 41092 KB Correct answer: answer = 7550
15 Correct 0 ms 41092 KB Correct answer: answer = 7220
16 Correct 0 ms 41092 KB Correct answer: answer = 7550
17 Correct 0 ms 41092 KB Correct answer: answer = 10000
18 Correct 0 ms 41092 KB Correct answer: answer = 10000
19 Correct 0 ms 41092 KB Correct answer: answer = 624
20 Correct 0 ms 41092 KB Correct answer: answer = 10000
21 Correct 0 ms 41092 KB Correct answer: answer = 1
22 Correct 0 ms 41092 KB Correct answer: answer = 4
23 Correct 0 ms 41092 KB Correct answer: answer = 1
24 Correct 0 ms 41092 KB Correct answer: answer = 5
25 Correct 0 ms 41092 KB Correct answer: answer = 41
26 Correct 0 ms 41092 KB Correct answer: answer = 71923
27 Correct 0 ms 41092 KB Correct answer: answer = 77137
28 Correct 0 ms 41092 KB Correct answer: answer = 764
29 Correct 0 ms 41092 KB Correct answer: answer = 250000
30 Correct 0 ms 41092 KB Correct answer: answer = 500
31 Correct 0 ms 41092 KB Correct answer: answer = 32
32 Correct 0 ms 41092 KB Correct answer: answer = 130050
33 Correct 0 ms 41092 KB Correct answer: answer = 5110
34 Correct 0 ms 41092 KB Correct answer: answer = 2626
35 Correct 0 ms 41092 KB Correct answer: answer = 796
36 Correct 0 ms 41092 KB Correct answer: answer = 7580
37 Correct 0 ms 41092 KB Correct answer: answer = 1904
38 Correct 0 ms 41092 KB Correct answer: answer = 996004
39 Correct 0 ms 41092 KB Correct answer: answer = 38817
40 Correct 0 ms 41092 KB Correct answer: answer = 4096
41 Correct 0 ms 41092 KB Correct answer: answer = 1
42 Correct 0 ms 41092 KB Correct answer: answer = 1
43 Correct 0 ms 41092 KB Correct answer: answer = 2040
44 Correct 0 ms 41092 KB Correct answer: answer = 2
45 Correct 0 ms 41092 KB Correct answer: answer = 4
46 Correct 0 ms 41092 KB Correct answer: answer = 9
47 Correct 0 ms 41092 KB Correct answer: answer = 9
48 Correct 0 ms 41092 KB Correct answer: answer = 21
49 Correct 0 ms 41092 KB Correct answer: answer = 71
50 Correct 0 ms 41092 KB Correct answer: answer = 77
51 Correct 0 ms 41092 KB Correct answer: answer = 400
52 Correct 0 ms 41092 KB Correct answer: answer = 996004
53 Correct 0 ms 41092 KB Correct answer: answer = 997310
54 Correct 0 ms 41092 KB Correct answer: answer = 990781
55 Correct 0 ms 41092 KB Correct answer: answer = 996545
56 Correct 0 ms 41092 KB Correct answer: answer = 484
57 Correct 0 ms 41092 KB Correct answer: answer = 484
58 Correct 0 ms 41092 KB Correct answer: answer = 63501
59 Correct 0 ms 41092 KB Correct answer: answer = 323501
60 Correct 0 ms 41092 KB Correct answer: answer = 752500
61 Correct 0 ms 41092 KB Correct answer: answer = 761480
62 Correct 0 ms 41092 KB Correct answer: answer = 758932
63 Correct 0 ms 41092 KB Correct answer: answer = 1000000
64 Correct 0 ms 41092 KB Correct answer: answer = 750500
65 Correct 0 ms 41092 KB Correct answer: answer = 1000000
66 Correct 0 ms 41092 KB Correct answer: answer = 250000
67 Correct 0 ms 41092 KB Correct answer: answer = 250000
68 Correct 0 ms 41092 KB Correct answer: answer = 1000000
69 Correct 0 ms 41092 KB Correct answer: answer = 994009
70 Correct 0 ms 41092 KB Correct answer: answer = 59315
71 Correct 0 ms 41092 KB Correct answer: answer = 25454
72 Correct 0 ms 41092 KB Correct answer: answer = 1504
73 Correct 0 ms 41092 KB Correct answer: answer = 37486
74 Correct 0 ms 41092 KB Correct answer: answer = 4284
75 Correct 0 ms 41092 KB Correct answer: answer = 158008
76 Correct 0 ms 41092 KB Correct answer: answer = 51860
77 Correct 0 ms 41092 KB Correct answer: answer = 12985
78 Correct 0 ms 41232 KB Correct answer: answer = 997864126212
79 Correct 0 ms 41232 KB Correct answer: answer = 998608411647
80 Correct 0 ms 41232 KB Correct answer: answer = 995265560477
81 Correct 0 ms 41232 KB Correct answer: answer = 10125000
82 Correct 0 ms 41232 KB Correct answer: answer = 2291668
83 Correct 0 ms 41232 KB Correct answer: answer = 42388
84 Correct 0 ms 41232 KB Correct answer: answer = 10318
85 Correct 3 ms 41232 KB Correct answer: answer = 3416
86 Correct 3 ms 41232 KB Correct answer: answer = 331708193881
87 Correct 0 ms 41232 KB Correct answer: answer = 2861193756
88 Correct 3 ms 41232 KB Correct answer: answer = 114646930
89 Correct 0 ms 41232 KB Correct answer: answer = 9280921
90 Correct 3 ms 41232 KB Correct answer: answer = 999984053400
91 Correct 3 ms 41232 KB Correct answer: answer = 750935949134
92 Correct 0 ms 41232 KB Correct answer: answer = 1000000000000
93 Correct 0 ms 41232 KB Correct answer: answer = 998762383161
94 Correct 3 ms 41232 KB Correct answer: answer = 23017412908
95 Correct 0 ms 41232 KB Correct answer: answer = 728143410622
96 Correct 0 ms 41232 KB Correct answer: answer = 2
97 Correct 3 ms 41232 KB Correct answer: answer = 1824916
98 Correct 3 ms 41232 KB Correct answer: answer = 10680029
99 Correct 0 ms 41232 KB Correct answer: answer = 18351700
100 Correct 0 ms 41232 KB Correct answer: answer = 16040026
101 Correct 0 ms 41232 KB Correct answer: answer = 253968628325
102 Correct 0 ms 41232 KB Correct answer: answer = 10267
103 Correct 0 ms 41232 KB Correct answer: answer = 2582408
104 Correct 0 ms 41232 KB Correct answer: answer = 78024964781
105 Correct 0 ms 41232 KB Correct answer: answer = 9866346457
106 Correct 0 ms 41232 KB Correct answer: answer = 3327720949
107 Correct 0 ms 41232 KB Correct answer: answer = 86064128360
108 Correct 0 ms 41232 KB Correct answer: answer = 12698259150
109 Correct 3 ms 41232 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41092 KB Correct answer: answer = 4
2 Correct 0 ms 41092 KB Correct answer: answer = 4
3 Correct 0 ms 41092 KB Correct answer: answer = 4
4 Correct 0 ms 41092 KB Correct answer: answer = 12
5 Correct 0 ms 41092 KB Correct answer: answer = 52
6 Correct 0 ms 41092 KB Correct answer: answer = 210
7 Correct 0 ms 41092 KB Correct answer: answer = 88
8 Correct 0 ms 41092 KB Correct answer: answer = 7696
9 Correct 0 ms 41092 KB Correct answer: answer = 1
10 Correct 0 ms 41092 KB Correct answer: answer = 2374
11 Correct 0 ms 41092 KB Correct answer: answer = 9502
12 Correct 0 ms 41092 KB Correct answer: answer = 49
13 Correct 0 ms 41092 KB Correct answer: answer = 151
14 Correct 0 ms 41092 KB Correct answer: answer = 7550
15 Correct 0 ms 41092 KB Correct answer: answer = 7220
16 Correct 0 ms 41092 KB Correct answer: answer = 7550
17 Correct 0 ms 41092 KB Correct answer: answer = 10000
18 Correct 0 ms 41092 KB Correct answer: answer = 10000
19 Correct 0 ms 41092 KB Correct answer: answer = 624
20 Correct 0 ms 41092 KB Correct answer: answer = 10000
21 Correct 0 ms 41092 KB Correct answer: answer = 1
22 Correct 0 ms 41092 KB Correct answer: answer = 4
23 Correct 0 ms 41092 KB Correct answer: answer = 1
24 Correct 0 ms 41092 KB Correct answer: answer = 5
25 Correct 0 ms 41092 KB Correct answer: answer = 41
26 Correct 0 ms 41092 KB Correct answer: answer = 71923
27 Correct 0 ms 41092 KB Correct answer: answer = 77137
28 Correct 0 ms 41092 KB Correct answer: answer = 764
29 Correct 0 ms 41092 KB Correct answer: answer = 250000
30 Correct 0 ms 41092 KB Correct answer: answer = 500
31 Correct 0 ms 41092 KB Correct answer: answer = 32
32 Correct 0 ms 41092 KB Correct answer: answer = 130050
33 Correct 0 ms 41092 KB Correct answer: answer = 5110
34 Correct 0 ms 41092 KB Correct answer: answer = 2626
35 Correct 0 ms 41092 KB Correct answer: answer = 796
36 Correct 0 ms 41092 KB Correct answer: answer = 7580
37 Correct 0 ms 41092 KB Correct answer: answer = 1904
38 Correct 0 ms 41092 KB Correct answer: answer = 996004
39 Correct 0 ms 41092 KB Correct answer: answer = 38817
40 Correct 0 ms 41092 KB Correct answer: answer = 4096
41 Correct 0 ms 41092 KB Correct answer: answer = 1
42 Correct 0 ms 41092 KB Correct answer: answer = 1
43 Correct 0 ms 41092 KB Correct answer: answer = 2040
44 Correct 0 ms 41092 KB Correct answer: answer = 2
45 Correct 0 ms 41092 KB Correct answer: answer = 4
46 Correct 0 ms 41092 KB Correct answer: answer = 9
47 Correct 0 ms 41092 KB Correct answer: answer = 9
48 Correct 0 ms 41092 KB Correct answer: answer = 21
49 Correct 0 ms 41092 KB Correct answer: answer = 71
50 Correct 0 ms 41092 KB Correct answer: answer = 77
51 Correct 0 ms 41092 KB Correct answer: answer = 400
52 Correct 0 ms 41092 KB Correct answer: answer = 996004
53 Correct 0 ms 41092 KB Correct answer: answer = 997310
54 Correct 0 ms 41092 KB Correct answer: answer = 990781
55 Correct 0 ms 41092 KB Correct answer: answer = 996545
56 Correct 0 ms 41092 KB Correct answer: answer = 484
57 Correct 0 ms 41092 KB Correct answer: answer = 484
58 Correct 0 ms 41092 KB Correct answer: answer = 63501
59 Correct 0 ms 41092 KB Correct answer: answer = 323501
60 Correct 0 ms 41092 KB Correct answer: answer = 752500
61 Correct 0 ms 41092 KB Correct answer: answer = 761480
62 Correct 0 ms 41092 KB Correct answer: answer = 758932
63 Correct 0 ms 41092 KB Correct answer: answer = 1000000
64 Correct 0 ms 41092 KB Correct answer: answer = 750500
65 Correct 0 ms 41092 KB Correct answer: answer = 1000000
66 Correct 0 ms 41092 KB Correct answer: answer = 250000
67 Correct 0 ms 41092 KB Correct answer: answer = 250000
68 Correct 0 ms 41092 KB Correct answer: answer = 1000000
69 Correct 0 ms 41092 KB Correct answer: answer = 994009
70 Correct 0 ms 41092 KB Correct answer: answer = 59315
71 Correct 0 ms 41092 KB Correct answer: answer = 25454
72 Correct 0 ms 41092 KB Correct answer: answer = 1504
73 Correct 0 ms 41092 KB Correct answer: answer = 37486
74 Correct 0 ms 41092 KB Correct answer: answer = 4284
75 Correct 0 ms 41092 KB Correct answer: answer = 158008
76 Correct 0 ms 41092 KB Correct answer: answer = 51860
77 Correct 0 ms 41092 KB Correct answer: answer = 12985
78 Correct 0 ms 41232 KB Correct answer: answer = 997864126212
79 Correct 0 ms 41232 KB Correct answer: answer = 998608411647
80 Correct 0 ms 41232 KB Correct answer: answer = 995265560477
81 Correct 0 ms 41232 KB Correct answer: answer = 10125000
82 Correct 0 ms 41232 KB Correct answer: answer = 2291668
83 Correct 0 ms 41232 KB Correct answer: answer = 42388
84 Correct 0 ms 41232 KB Correct answer: answer = 10318
85 Correct 3 ms 41232 KB Correct answer: answer = 3416
86 Correct 3 ms 41232 KB Correct answer: answer = 331708193881
87 Correct 0 ms 41232 KB Correct answer: answer = 2861193756
88 Correct 3 ms 41232 KB Correct answer: answer = 114646930
89 Correct 0 ms 41232 KB Correct answer: answer = 9280921
90 Correct 3 ms 41232 KB Correct answer: answer = 999984053400
91 Correct 3 ms 41232 KB Correct answer: answer = 750935949134
92 Correct 0 ms 41232 KB Correct answer: answer = 1000000000000
93 Correct 0 ms 41232 KB Correct answer: answer = 998762383161
94 Correct 3 ms 41232 KB Correct answer: answer = 23017412908
95 Correct 0 ms 41232 KB Correct answer: answer = 728143410622
96 Correct 0 ms 41232 KB Correct answer: answer = 2
97 Correct 3 ms 41232 KB Correct answer: answer = 1824916
98 Correct 3 ms 41232 KB Correct answer: answer = 10680029
99 Correct 0 ms 41232 KB Correct answer: answer = 18351700
100 Correct 0 ms 41232 KB Correct answer: answer = 16040026
101 Correct 0 ms 41232 KB Correct answer: answer = 253968628325
102 Correct 0 ms 41232 KB Correct answer: answer = 10267
103 Correct 0 ms 41232 KB Correct answer: answer = 2582408
104 Correct 0 ms 41232 KB Correct answer: answer = 78024964781
105 Correct 0 ms 41232 KB Correct answer: answer = 9866346457
106 Correct 0 ms 41232 KB Correct answer: answer = 3327720949
107 Correct 0 ms 41232 KB Correct answer: answer = 86064128360
108 Correct 0 ms 41232 KB Correct answer: answer = 12698259150
109 Correct 3 ms 41232 KB Correct answer: answer = 1185259288
110 Correct 23 ms 41876 KB Correct answer: answer = 999889968863
111 Correct 23 ms 41876 KB Correct answer: answer = 999861384931
112 Correct 26 ms 41876 KB Correct answer: answer = 999811809929
113 Correct 23 ms 41876 KB Correct answer: answer = 999869756441
114 Correct 23 ms 42980 KB Correct answer: answer = 1700000000
115 Correct 33 ms 42980 KB Correct answer: answer = 131666670
116 Correct 3 ms 41684 KB Correct answer: answer = 89478486
117 Correct 9 ms 41684 KB Correct answer: answer = 4971040
118 Correct 13 ms 41684 KB Correct answer: answer = 2711494
119 Correct 36 ms 42980 KB Correct answer: answer = 25252530
120 Correct 26 ms 42980 KB Correct answer: answer = 62500000
121 Correct 26 ms 42980 KB Correct answer: answer = 333175097780
122 Correct 39 ms 42980 KB Correct answer: answer = 33121180179
123 Correct 53 ms 42980 KB Correct answer: answer = 9802314015
124 Correct 43 ms 42980 KB Correct answer: answer = 32567551
125 Correct 53 ms 42980 KB Correct answer: answer = 997525000000
126 Correct 59 ms 42980 KB Correct answer: answer = 752723538884
127 Correct 19 ms 41876 KB Correct answer: answer = 1000000000000
128 Correct 29 ms 41876 KB Correct answer: answer = 999978000121
129 Correct 23 ms 41876 KB Correct answer: answer = 745986144735
130 Correct 3 ms 41876 KB Correct answer: answer = 2
131 Correct 39 ms 42980 KB Correct answer: answer = 277966670
132 Correct 23 ms 42980 KB Correct answer: answer = 2500900082
133 Correct 23 ms 42084 KB Correct answer: answer = 301248349636
134 Correct 23 ms 42076 KB Correct answer: answer = 14118891
135 Correct 26 ms 41876 KB Correct answer: answer = 14384977265
136 Correct 26 ms 41876 KB Correct answer: answer = 3681368330
137 Correct 23 ms 41876 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41092 KB Correct answer: answer = 4
2 Correct 0 ms 41092 KB Correct answer: answer = 4
3 Correct 0 ms 41092 KB Correct answer: answer = 4
4 Correct 0 ms 41092 KB Correct answer: answer = 12
5 Correct 0 ms 41092 KB Correct answer: answer = 52
6 Correct 0 ms 41092 KB Correct answer: answer = 210
7 Correct 0 ms 41092 KB Correct answer: answer = 88
8 Correct 0 ms 41092 KB Correct answer: answer = 7696
9 Correct 0 ms 41092 KB Correct answer: answer = 1
10 Correct 0 ms 41092 KB Correct answer: answer = 2374
11 Correct 0 ms 41092 KB Correct answer: answer = 9502
12 Correct 0 ms 41092 KB Correct answer: answer = 49
13 Correct 0 ms 41092 KB Correct answer: answer = 151
14 Correct 0 ms 41092 KB Correct answer: answer = 7550
15 Correct 0 ms 41092 KB Correct answer: answer = 7220
16 Correct 0 ms 41092 KB Correct answer: answer = 7550
17 Correct 0 ms 41092 KB Correct answer: answer = 10000
18 Correct 0 ms 41092 KB Correct answer: answer = 10000
19 Correct 0 ms 41092 KB Correct answer: answer = 624
20 Correct 0 ms 41092 KB Correct answer: answer = 10000
21 Correct 0 ms 41092 KB Correct answer: answer = 1
22 Correct 0 ms 41092 KB Correct answer: answer = 4
23 Correct 0 ms 41092 KB Correct answer: answer = 1
24 Correct 0 ms 41092 KB Correct answer: answer = 5
25 Correct 0 ms 41092 KB Correct answer: answer = 41
26 Correct 0 ms 41092 KB Correct answer: answer = 71923
27 Correct 0 ms 41092 KB Correct answer: answer = 77137
28 Correct 0 ms 41092 KB Correct answer: answer = 764
29 Correct 0 ms 41092 KB Correct answer: answer = 250000
30 Correct 0 ms 41092 KB Correct answer: answer = 500
31 Correct 0 ms 41092 KB Correct answer: answer = 32
32 Correct 0 ms 41092 KB Correct answer: answer = 130050
33 Correct 0 ms 41092 KB Correct answer: answer = 5110
34 Correct 0 ms 41092 KB Correct answer: answer = 2626
35 Correct 0 ms 41092 KB Correct answer: answer = 796
36 Correct 0 ms 41092 KB Correct answer: answer = 7580
37 Correct 0 ms 41092 KB Correct answer: answer = 1904
38 Correct 0 ms 41092 KB Correct answer: answer = 996004
39 Correct 0 ms 41092 KB Correct answer: answer = 38817
40 Correct 0 ms 41092 KB Correct answer: answer = 4096
41 Correct 0 ms 41092 KB Correct answer: answer = 1
42 Correct 0 ms 41092 KB Correct answer: answer = 1
43 Correct 0 ms 41092 KB Correct answer: answer = 2040
44 Correct 0 ms 41092 KB Correct answer: answer = 2
45 Correct 0 ms 41092 KB Correct answer: answer = 4
46 Correct 0 ms 41092 KB Correct answer: answer = 9
47 Correct 0 ms 41092 KB Correct answer: answer = 9
48 Correct 0 ms 41092 KB Correct answer: answer = 21
49 Correct 0 ms 41092 KB Correct answer: answer = 71
50 Correct 0 ms 41092 KB Correct answer: answer = 77
51 Correct 0 ms 41092 KB Correct answer: answer = 400
52 Correct 0 ms 41092 KB Correct answer: answer = 996004
53 Correct 0 ms 41092 KB Correct answer: answer = 997310
54 Correct 0 ms 41092 KB Correct answer: answer = 990781
55 Correct 0 ms 41092 KB Correct answer: answer = 996545
56 Correct 0 ms 41092 KB Correct answer: answer = 484
57 Correct 0 ms 41092 KB Correct answer: answer = 484
58 Correct 0 ms 41092 KB Correct answer: answer = 63501
59 Correct 0 ms 41092 KB Correct answer: answer = 323501
60 Correct 0 ms 41092 KB Correct answer: answer = 752500
61 Correct 0 ms 41092 KB Correct answer: answer = 761480
62 Correct 0 ms 41092 KB Correct answer: answer = 758932
63 Correct 0 ms 41092 KB Correct answer: answer = 1000000
64 Correct 0 ms 41092 KB Correct answer: answer = 750500
65 Correct 0 ms 41092 KB Correct answer: answer = 1000000
66 Correct 0 ms 41092 KB Correct answer: answer = 250000
67 Correct 0 ms 41092 KB Correct answer: answer = 250000
68 Correct 0 ms 41092 KB Correct answer: answer = 1000000
69 Correct 0 ms 41092 KB Correct answer: answer = 994009
70 Correct 0 ms 41092 KB Correct answer: answer = 59315
71 Correct 0 ms 41092 KB Correct answer: answer = 25454
72 Correct 0 ms 41092 KB Correct answer: answer = 1504
73 Correct 0 ms 41092 KB Correct answer: answer = 37486
74 Correct 0 ms 41092 KB Correct answer: answer = 4284
75 Correct 0 ms 41092 KB Correct answer: answer = 158008
76 Correct 0 ms 41092 KB Correct answer: answer = 51860
77 Correct 0 ms 41092 KB Correct answer: answer = 12985
78 Correct 0 ms 41232 KB Correct answer: answer = 997864126212
79 Correct 0 ms 41232 KB Correct answer: answer = 998608411647
80 Correct 0 ms 41232 KB Correct answer: answer = 995265560477
81 Correct 0 ms 41232 KB Correct answer: answer = 10125000
82 Correct 0 ms 41232 KB Correct answer: answer = 2291668
83 Correct 0 ms 41232 KB Correct answer: answer = 42388
84 Correct 0 ms 41232 KB Correct answer: answer = 10318
85 Correct 3 ms 41232 KB Correct answer: answer = 3416
86 Correct 3 ms 41232 KB Correct answer: answer = 331708193881
87 Correct 0 ms 41232 KB Correct answer: answer = 2861193756
88 Correct 3 ms 41232 KB Correct answer: answer = 114646930
89 Correct 0 ms 41232 KB Correct answer: answer = 9280921
90 Correct 3 ms 41232 KB Correct answer: answer = 999984053400
91 Correct 3 ms 41232 KB Correct answer: answer = 750935949134
92 Correct 0 ms 41232 KB Correct answer: answer = 1000000000000
93 Correct 0 ms 41232 KB Correct answer: answer = 998762383161
94 Correct 3 ms 41232 KB Correct answer: answer = 23017412908
95 Correct 0 ms 41232 KB Correct answer: answer = 728143410622
96 Correct 0 ms 41232 KB Correct answer: answer = 2
97 Correct 3 ms 41232 KB Correct answer: answer = 1824916
98 Correct 3 ms 41232 KB Correct answer: answer = 10680029
99 Correct 0 ms 41232 KB Correct answer: answer = 18351700
100 Correct 0 ms 41232 KB Correct answer: answer = 16040026
101 Correct 0 ms 41232 KB Correct answer: answer = 253968628325
102 Correct 0 ms 41232 KB Correct answer: answer = 10267
103 Correct 0 ms 41232 KB Correct answer: answer = 2582408
104 Correct 0 ms 41232 KB Correct answer: answer = 78024964781
105 Correct 0 ms 41232 KB Correct answer: answer = 9866346457
106 Correct 0 ms 41232 KB Correct answer: answer = 3327720949
107 Correct 0 ms 41232 KB Correct answer: answer = 86064128360
108 Correct 0 ms 41232 KB Correct answer: answer = 12698259150
109 Correct 3 ms 41232 KB Correct answer: answer = 1185259288
110 Correct 23 ms 41876 KB Correct answer: answer = 999889968863
111 Correct 23 ms 41876 KB Correct answer: answer = 999861384931
112 Correct 26 ms 41876 KB Correct answer: answer = 999811809929
113 Correct 23 ms 41876 KB Correct answer: answer = 999869756441
114 Correct 23 ms 42980 KB Correct answer: answer = 1700000000
115 Correct 33 ms 42980 KB Correct answer: answer = 131666670
116 Correct 3 ms 41684 KB Correct answer: answer = 89478486
117 Correct 9 ms 41684 KB Correct answer: answer = 4971040
118 Correct 13 ms 41684 KB Correct answer: answer = 2711494
119 Correct 36 ms 42980 KB Correct answer: answer = 25252530
120 Correct 26 ms 42980 KB Correct answer: answer = 62500000
121 Correct 26 ms 42980 KB Correct answer: answer = 333175097780
122 Correct 39 ms 42980 KB Correct answer: answer = 33121180179
123 Correct 53 ms 42980 KB Correct answer: answer = 9802314015
124 Correct 43 ms 42980 KB Correct answer: answer = 32567551
125 Correct 53 ms 42980 KB Correct answer: answer = 997525000000
126 Correct 59 ms 42980 KB Correct answer: answer = 752723538884
127 Correct 19 ms 41876 KB Correct answer: answer = 1000000000000
128 Correct 29 ms 41876 KB Correct answer: answer = 999978000121
129 Correct 23 ms 41876 KB Correct answer: answer = 745986144735
130 Correct 3 ms 41876 KB Correct answer: answer = 2
131 Correct 39 ms 42980 KB Correct answer: answer = 277966670
132 Correct 23 ms 42980 KB Correct answer: answer = 2500900082
133 Correct 23 ms 42084 KB Correct answer: answer = 301248349636
134 Correct 23 ms 42076 KB Correct answer: answer = 14118891
135 Correct 26 ms 41876 KB Correct answer: answer = 14384977265
136 Correct 26 ms 41876 KB Correct answer: answer = 3681368330
137 Correct 23 ms 41876 KB Correct answer: answer = 2720316816
138 Correct 39 ms 42660 KB Correct answer: answer = 999976000144
139 Correct 43 ms 42660 KB Correct answer: answer = 999856102410
140 Correct 43 ms 42660 KB Correct answer: answer = 999958401531
141 Correct 43 ms 42660 KB Correct answer: answer = 999769649944
142 Correct 36 ms 42660 KB Correct answer: answer = 999874525918
143 Correct 53 ms 44788 KB Correct answer: answer = 6050000000
144 Correct 63 ms 44788 KB Correct answer: answer = 1112500000
145 Correct 26 ms 43236 KB Correct answer: answer = 4294967296
146 Correct 49 ms 43236 KB Correct answer: answer = 87652406
147 Correct 63 ms 43236 KB Correct answer: answer = 6297664
148 Correct 49 ms 43236 KB Correct answer: answer = 196612
149 Correct 83 ms 44788 KB Correct answer: answer = 15015100
150 Correct 73 ms 44788 KB Correct answer: answer = 25000000
151 Correct 43 ms 44788 KB Correct answer: answer = 333230209550
152 Correct 113 ms 44788 KB Correct answer: answer = 917123769
153 Correct 159 ms 44788 KB Correct answer: answer = 95162
154 Correct 73 ms 44788 KB Correct answer: answer = 382616191
155 Correct 86 ms 44788 KB Correct answer: answer = 990033333400
156 Correct 106 ms 44788 KB Correct answer: answer = 990000100000
157 Correct 149 ms 44788 KB Correct answer: answer = 749998188180
158 Correct 36 ms 42660 KB Correct answer: answer = 1000000000000
159 Correct 43 ms 42660 KB Correct answer: answer = 999988000036
160 Correct 43 ms 42660 KB Correct answer: answer = 744929274393
161 Correct 19 ms 42660 KB Correct answer: answer = 2
162 Correct 116 ms 44788 KB Correct answer: answer = 1300024
163 Correct 49 ms 44788 KB Correct answer: answer = 5000700010
164 Correct 43 ms 42996 KB Correct answer: answer = 354997100800
165 Correct 83 ms 42980 KB Correct answer: answer = 257000
166 Correct 69 ms 42980 KB Correct answer: answer = 3765323
167 Correct 69 ms 42980 KB Correct answer: answer = 1525903
168 Correct 59 ms 42660 KB Correct answer: answer = 67618137730
169 Correct 56 ms 42660 KB Correct answer: answer = 12656680171
170 Correct 39 ms 42800 KB Correct answer: answer = 579831736
171 Correct 93 ms 43252 KB Correct answer: answer = 23605611
172 Correct 53 ms 42800 KB Correct answer: answer = 7052481200
173 Correct 53 ms 42996 KB Correct answer: answer = 1314039500
174 Correct 63 ms 43252 KB Correct answer: answer = 302484000
175 Correct 86 ms 43764 KB Correct answer: answer = 52348480