QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222035 | #7608. Cliques | ucup-team088# | AC ✓ | 549ms | 140588kb | C++17 | 15.6kb | 2023-10-21 15:31:10 | 2023-10-21 15:31:10 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
#include<chrono>
using namespace std;
//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
//ll mod = 1;
//constexpr ll mod = 998244353;
constexpr ll mod = 1000000007;
const int mod17 = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
using ld = double;
typedef pair<ld, ld> LDP;
const ld eps = 1e-10;
const ld pi = acosl(-1.0);
template<typename T>
void chmin(T& a, T b) {
a = min(a, b);
}
template<typename T>
void chmax(T& a, T b) {
a = max(a, b);
}
template<typename T>
vector<T> vmerge(vector<T>& a, vector<T>& b) {
vector<T> res;
int ida = 0, idb = 0;
while (ida < a.size() || idb < b.size()) {
if (idb == b.size()) {
res.push_back(a[ida]); ida++;
}
else if (ida == a.size()) {
res.push_back(b[idb]); idb++;
}
else {
if (a[ida] < b[idb]) {
res.push_back(a[ida]); ida++;
}
else {
res.push_back(b[idb]); idb++;
}
}
}
return res;
}
template<typename T>
void cinarray(vector<T>& v) {
rep(i, v.size())cin >> v[i];
}
template<typename T>
void coutarray(vector<T>& v) {
rep(i, v.size()) {
if (i > 0)cout << " "; cout << v[i];
}
cout << "\n";
}
ll mod_pow(ll x, ll n, ll m = mod) {
if (n < 0) {
ll res = mod_pow(x, -n, m);
return mod_pow(res, m - 2, m);
}
if (abs(x) >= m)x %= m;
if (x < 0)x += m;
//if (x == 0)return 0;
ll res = 1;
while (n) {
if (n & 1)res = res * x % m;
x = x * x % m; n >>= 1;
}
return res;
}
//mod should be <2^31
struct modint {
int n;
modint() :n(0) { ; }
modint(ll m) {
if (m < 0 || mod <= m) {
m %= mod; if (m < 0)m += mod;
}
n = m;
}
operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
if (n == 0)return modint(1);
modint res = (a * a) ^ (n / 2);
if (n % 2)res = res * a;
return res;
}
ll inv(ll a, ll p) {
return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) { a = a / b; return a; }
const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
fact[0] = modint(1);
for (int i = 0; i < max_n - 1; i++) {
fact[i + 1] = fact[i] * modint(i + 1);
}
factinv[max_n - 1] = modint(1) / fact[max_n - 1];
for (int i = max_n - 2; i >= 0; i--) {
factinv[i] = factinv[i + 1] * modint(i + 1);
}
}
modint comb(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[a - b];
}
ll gcd(ll a, ll b) {
a = abs(a); b = abs(b);
if (a < b)swap(a, b);
while (b) {
ll r = a % b; a = b; b = r;
}
return a;
}
template<typename T>
void addv(vector<T>& v, int loc, T val) {
if (loc >= v.size())v.resize(loc + 1, 0);
v[loc] += val;
}
/*const int mn = 2000005;
bool isp[mn];
vector<int> ps;
void init() {
fill(isp + 2, isp + mn, true);
for (int i = 2; i < mn; i++) {
if (!isp[i])continue;
ps.push_back(i);
for (int j = 2 * i; j < mn; j += i) {
isp[j] = false;
}
}
}*/
//[,val)
template<typename T>
auto prev_itr(set<T>& st, T val) {
auto res = st.lower_bound(val);
if (res == st.begin())return st.end();
res--; return res;
}
//[val,)
template<typename T>
auto next_itr(set<T>& st, T val) {
auto res = st.lower_bound(val);
return res;
}
using mP = pair<modint, modint>;
mP operator+(mP a, mP b) {
return { a.first + b.first,a.second + b.second };
}
mP operator+=(mP& a, mP b) {
a = a + b; return a;
}
mP operator-(mP a, mP b) {
return { a.first - b.first,a.second - b.second };
}
mP operator-=(mP& a, mP b) {
a = a - b; return a;
}
LP operator+(LP a, LP b) {
return { a.first + b.first,a.second + b.second };
}
LP operator+=(LP& a, LP b) {
a = a + b; return a;
}
LP operator-(LP a, LP b) {
return { a.first - b.first,a.second - b.second };
}
LP operator-=(LP& a, LP b) {
a = a - b; return a;
}
mt19937 mt(time(0));
const string drul = "DRUL";
string senw = "SENW";
//DRUL,or SENW
//int dx[4] = { 1,0,-1,0 };
//int dy[4] = { 0,1,0,-1 };
//------------------------------------
#define ftt function<T(T,T)>
#define ftu function<T(T,U,int,int)>
#define fuu function<U(U,U)>
template<typename T, typename U>
struct SegT {
private:
int n;
vector<T> node;
vector<U> lazy;
T et; U eu;
ftt f;
ftu g;
fuu h;
public:
void init(vector<T> ori, T _et, U _eu, ftt _f, ftu _g, fuu _h) {
int sz = ori.size();
et = _et, eu = _eu; f = _f, g = _g, h = _h;
n = 1;
while (n < sz)n <<= 1;
node.resize(2 * n - 1, et);
lazy.resize(2 * n - 1, eu);
rep(i, sz) {
node[i + n - 1] = ori[i];
}
per(i, n - 1) {
node[i] = f(node[2 * i + 1], node[2 * i + 2]);
}
}
SegT() { ; }
void init(int sz, T _et, U _eu, ftt _f, ftu _g, fuu _h) {
et = _et, eu = _eu; f = _f, g = _g, h = _h;
n = 1;
while (n < sz)n <<= 1;
node.resize(2 * n - 1, et);
lazy.resize(2 * n - 1, eu);
}
void eval(int k, int l, int r) {
if (lazy[k] == eu)return;
node[k] = g(node[k], lazy[k], l, r);
if (r - l > 1) {
lazy[2 * k + 1] = h(lazy[k], lazy[2 * k + 1]);
lazy[2 * k + 2] = h(lazy[k], lazy[2 * k + 2]);
}
lazy[k] = eu;
}
void add(U x, int a, int b, int k = 0, int l = 0, int r = -1) {
if (r < 0)r = n;
eval(k, l, r);
if (r <= a || b <= l)return;
if (a <= l && r <= b) {
lazy[k] = h(x, lazy[k]);
eval(k, l, r);
}
else {
add(x, a, b, k * 2 + 1, l, (l + r) / 2);
add(x, a, b, k * 2 + 2, (l + r) / 2, r);
node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
}
}
T query(int a, int b, int k = 0, int l = 0, int r = -1) {
if (r < 0)r = n;
eval(k, l, r);
if (r <= a || b <= l)return et;
if (a <= l && r <= b)return node[k];
else {
T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return f(vl, vr);
}
}
void update(int loc, T x) {
int k = 0, l = 0, r = n;
stack<P> st;
while (k < n - 1) {
eval(k, l, r);
st.push({ l,r });
if (loc < (l + r) / 2) {
k = 2 * k + 1;
r = (l + r) / 2;
}
else {
k = 2 * k + 2;
l = (l + r) / 2;
}
}
eval(k, l, r);
st.push({ l,r });
node[k] = x;
while (k > 0) {
k = (k - 1) / 2;
st.pop();
l = st.top().first, r = st.top().second;
eval(2 * k + 1, l, (l + r) / 2);
eval(2 * k + 2, (l + r) / 2, r);
node[k] = f(node[2 * k + 1], node[2 * k + 2]);
}
}
//k以上でf(x,node[y+sz-1])をtrueにするような最小のy
int searchloc(int le, T x, function<bool(T, T)> comp) {
int k = 0, l = 0, r = n;
while (k < n - 1) {
eval(k, l, r);
int m = (l + r) / 2;
if (le < m) {
k = 2 * k + 1; r = m;
}
else {
k = 2 * k + 2; l = m;
}
}
assert(k == le + n - 1);
eval(k, l, r);
if (comp(x, node[k]))return le;
//x=f(x,node[k]);
while (k > 0) {
int mem = k;
k = (k - 1) / 2;
if (2 * k + 1 == mem) {
r += r - l;
}
else {
l -= r - l;
}
if (2 * k + 1 == mem) {
eval(2 * k + 2, (l + r) / 2, r);
if (comp(x, node[2 * k + 2])) {
k = 2 * k + 2;
l = (l + r) / 2;
break;
}
//x=f(x,node[2*k+2]);
}
}
if (k == 0)return n;
while (k < n - 1) {
eval(2 * k + 1, l, (l + r) / 2);
eval(2 * k + 2, (l + r) / 2, r);
if (comp(x, node[2 * k + 1])) {
k = 2 * k + 1;
r = (l + r) / 2;
}
else {
k = 2 * k + 2;
l = (l + r) / 2;
//x=f(x,node[2*k+1]);
}
}
return k - (n - 1);
}
};
struct edge {
int to;
};
using edges = vector<edge>;
using Graph = vector<edges>;
struct HLDecomposition {
struct Chain {
int depth;
P parent;//chain number,index
vector<P> child;//child chain number,parent index
vector<int> mapfrom;
SegT<modint, modint> stree;
Chain() { ; }
Chain(int n) {
vector<modint> ori(n, 1);
function<modint(modint, modint)> f = [&](modint a, modint b) {
return a + b;
};
function<modint(modint, modint, int, int)> g = [&](modint a, modint b, int l, int r) {
a *= b; return a;
};
function<modint(modint, modint)> h = [&](modint a, modint b) {
return a * b;
};
stree.init(ori, 0, 1, f, g, h);
}
};
Graph baseG;
vector<Chain> chains;
vector<P> mapto;//raw index->chain number &index
vector<vector<int>> mapfrom;//chain number & index ->raw index
HLDecomposition() { ; }
HLDecomposition(const Graph& g) {
baseG = g;
const int n = baseG.size();
mapto = vector<P>(n, P{ -1,-1 });
mapfrom.clear();
vector<int> sz(n, 0);
int start = 0;
//int start = -1;
//rep(i, n)if (baseG[i].size() <= 1) { start = i; break; }
//assert(start != -1);
size_check_bfs(start, sz);
decomposition(start, start, 0, 0, 0, sz);
}
int depth(int t) {
return chains[mapto[t].first].depth;
}
private:
void size_check_bfs(int start, vector<int>& sz) {
const int n = baseG.size();
queue<P> que;
que.push({ start,start });
int cnt = 0; vector<int> ord(n, -1);
while (!que.empty()) {
int from, parent;
tie(from, parent) = que.front(); que.pop();
ord[cnt++] = from;
for (edge e : baseG[from]) {
if (e.to == parent)continue;
que.push({ e.to,from });
}
}
//assert(cnt == n);
reverse(all(ord));
rep(i, n) {
int from = ord[i];
sz[from] = 1; for (edge e : baseG[from])sz[from] += sz[e.to];
}
}
int decomposition(int from, int parent, int depth, int pnumber, int pindex, const vector<int>& sz) {
vector<int> seq;
bfs(from, parent, seq, sz);
const int c = chains.size();
chains.push_back(Chain((int)seq.size()));
//chains.push_back(Chain());
chains[c].depth = depth;
chains[c].parent = { pnumber,pindex };
rep(i, seq.size()) {
mapto[seq[i]] = { c,i };
chains[c].mapfrom.push_back(seq[i]);
}
mapfrom.push_back(chains[c].mapfrom);
rep(i, seq.size()) {
for (edge e : baseG[seq[i]]) {
if (mapto[e.to].first != -1)continue;
int nc = decomposition(e.to, seq[i], depth + 1, c, i, sz);
chains[c].child.push_back({ nc,i });
}
}
return c;
}
void bfs(int from, int parent, vector<int>& seq, const vector<int>& sz) {
for (;;) {
seq.push_back(from);
int best = -1, next = -1;
for (edge e : baseG[from]) {
if (e.to == parent)continue;
if (best < sz[e.to]) {
best = sz[e.to]; next = e.to;
}
}
if (next == -1)break;
parent = from; from = next;
}
}
vector<pair<int, P>> all_edge(int u, int v) {
vector<pair<int, P>> res;
if (depth(u) > depth(v))swap(u, v);
while (depth(v) > depth(u)) {
res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
P par = chains[mapto[v].first].parent;
v = mapfrom[par.first][par.second];
}
while (mapto[v].first != mapto[u].first) {
res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
P par = chains[mapto[v].first].parent;
v = mapfrom[par.first][par.second];
res.push_back({ mapto[u].first,{ 0,mapto[u].second + 1 } });
par = chains[mapto[u].first].parent;
u = mapfrom[par.first][par.second];
}
P p = minmax(mapto[v].second, mapto[u].second);
res.push_back({ mapto[v].first,{ p.first + 1,p.second + 1 } });
return res;
}
vector<pair<int, P>> all_vertice(int u, int v) {
vector<pair<int, P>> res;
if (depth(u) > depth(v))swap(u, v);
while (depth(v) > depth(u)) {
res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
P par = chains[mapto[v].first].parent;
v = mapfrom[par.first][par.second];
}
while (mapto[v].first != mapto[u].first) {
res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
P par = chains[mapto[v].first].parent;
v = mapfrom[par.first][par.second];
res.push_back({ mapto[u].first,{ 0,mapto[u].second + 1 } });
par = chains[mapto[u].first].parent;
u = mapfrom[par.first][par.second];
}
P p = minmax(mapto[v].second, mapto[u].second);
res.push_back({ mapto[v].first,{ p.first,p.second + 1 } });
return res;
}
public:
int lca(int u, int v) {
if (depth(u) > depth(v))swap(u, v);
while (depth(v) > depth(u)) {
P par = chains[mapto[v].first].parent;
v = mapfrom[par.first][par.second];
}
while (mapto[v].first != mapto[u].first) {
P par = chains[mapto[v].first].parent;
v = mapfrom[par.first][par.second];
par = chains[mapto[u].first].parent;
u = mapfrom[par.first][par.second];
}
if (mapto[v].second < mapto[u].second) {
return v;
}
return u;
}
modint vertice_add(int u, int v, modint a) {
modint res = 0;
vector<pair<int, P>> vs = all_vertice(u, v);
rep(i, vs.size()) {
int id = vs[i].first;
int l = vs[i].second.first; int r = vs[i].second.second;
res += chains[id].stree.query(l, r);
chains[id].stree.add(a, l, r);
}
return res;
}
};
void solve() {
int n; cin >> n;
Graph g(n);
rep(i, n - 1) {
int a, b; cin >> a >> b; a--; b--;
g[a].push_back({ b });
g[b].push_back({ a });
}
HLDecomposition hldl(g), hldr(g);
modint sl = n, sr = n;
modint inv2 = (1 + mod) / 2;
int q; cin >> q;
rep(i, q) {
char c; cin >> c;
int a, b; cin >> a >> b; a--; b--;
if (c == '+') {
modint val = hldl.vertice_add(a, b,2);
sl += val;
val = hldr.vertice_add(a, b, 2);
sr += val;
int l = hldr.lca(a, b);
val = hldr.vertice_add(l, l, inv2);
sr -= val * inv2;
}
else {
modint val = hldl.vertice_add(a, b, inv2);
sl -= val*inv2;
val = hldr.vertice_add(a, b, inv2);
sr -= val*inv2;
int l = hldr.lca(a, b);
val = hldr.vertice_add(l, l, 2);
sr += val;
}
modint ans = sl - sr;
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
//cout << fixed<<setprecision(10);
//init_f();
//init();
//init2();
//while(true)
//expr();
//int t; cin >> t; rep(i, t)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 11836kb
input:
5 1 2 5 1 2 3 4 2 6 + 4 5 + 2 2 + 1 3 - 2 2 + 2 3 + 4 4
output:
1 3 7 3 7 9
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 11788kb
input:
20 8 7 19 10 12 14 3 16 17 13 7 10 5 6 1 9 15 12 5 2 16 13 3 11 20 14 18 6 1 14 16 20 11 10 3 4 20 6 30 + 10 20 + 14 20 + 12 17 - 14 20 - 12 17 + 4 6 + 8 20 + 3 6 - 10 20 + 2 17 + 1 16 + 6 10 + 9 10 + 5 15 + 7 8 - 7 8 + 2 5 + 3 18 + 1 20 + 8 16 - 3 18 - 5 15 + 4 20 + 14 16 - 4 6 + 8 19 + 4 7 - 1 16 ...
output:
1 3 7 3 1 3 7 15 7 15 31 63 127 255 257 255 259 515 1027 1283 643 385 769 1537 769 785 865 481 737 369
result:
ok 30 lines
Test #3:
score: 0
Accepted
time: 269ms
memory: 44700kb
input:
131072 3641 72511 10338 18718 8949 15478 79108 62887 42154 28540 65359 102645 93744 48493 3277 103211 43542 61315 93315 118634 24021 57937 31034 436 30411 6208 1388 25159 93424 128520 119820 87281 5860 97559 59648 8225 57244 58766 119685 13716 130165 60958 79806 116338 97486 80167 101963 95499 51263...
output:
1 2 4 8 13 27 43 67 119 215 359 423 847 1167 1935 2447 2975 4511 5023 8639 6911 13759 12991 15103 23295 43775 47999 91647 85375 167295 169343 301695 600703 666239 1332351 2664575 2678911 2687103 5374207 5898495 11731455 11731967 22283263 22807551 21955327 43910399 43911423 44207359 44207360 44469504...
result:
ok 46368 lines
Test #4:
score: 0
Accepted
time: 301ms
memory: 77020kb
input:
131073 52869 122762 63296 22816 9889 23435 9452 109352 95210 125504 104234 105533 42422 123259 31189 77343 88679 25422 13860 61424 49617 27681 71743 44108 2612 55383 89088 79225 49508 86216 45176 26493 60940 104568 10733 11047 118351 29678 6184 107897 69675 73910 39495 78910 14871 125941 64731 68683...
output:
1 3 7 11 15 19 31 35 71 143 287 511 1023 1031 1991 1031 1287 1927 2055 3151 4687 4943 9295 17999 18959 37775 73759 74559 148031 148095 296191 151743 160063 110399 110463 127103 63615 63679 64191 90303 138431 212479 212607 423551 423583 426527 770591 865599 1054015 1794879 3587647 3587903 5168959 743...
result:
ok 38380 lines
Test #5:
score: 0
Accepted
time: 303ms
memory: 79084kb
input:
131072 110424 92279 34180 5104 64611 102341 17972 86901 20410 11042 71530 94889 66017 30180 70335 127390 32167 60823 78004 53470 19518 71917 13638 77859 126902 86404 129728 102154 94425 4299 65248 60503 30607 39590 122443 91908 131032 83134 74541 32476 57016 45547 99821 43007 46700 115397 61041 7605...
output:
1 3 4 8 10 12 18 30 32 43 85 133 267 535 791 927 1567 1663 1791 2111 3391 4031 8063 4031 8063 10111 11263 22527 22543 36879 73487 146959 165391 185871 300559 272655 273183 448031 224015 252431 256527 440847 459279 501791 623647 1069087 1265695 2451487 2455583 4911167 3469375 4341823 4620351 7536767 ...
result:
ok 41717 lines
Test #6:
score: 0
Accepted
time: 348ms
memory: 80160kb
input:
131073 67110 38301 121636 116046 93081 73335 44685 130771 105514 33619 39372 105681 75426 78839 116548 46901 69485 76621 124381 35376 22485 127299 100526 68870 59214 63623 65534 67039 7351 74453 99617 88460 99785 107786 105070 57072 122179 1357 125230 70014 95838 127074 119211 24691 41698 112488 502...
output:
1 3 5 11 13 14 18 28 40 52 60 62 122 210 340 532 1032 1192 1448 1968 3393 3391 5471 5631 10303 11071 11199 13183 26239 52223 52735 53759 69375 113407 117503 232191 236287 470271 748799 748807 1410567 2790919 1676807 3155975 6178823 6026759 6068743 12075527 20988423 21185031 42340871 42332419 8409549...
result:
ok 42683 lines
Test #7:
score: 0
Accepted
time: 358ms
memory: 79940kb
input:
131071 73178 110293 100318 26012 15854 39905 73704 8141 15422 88351 37522 86820 75177 113252 27007 40876 114342 57373 114214 99629 77119 106699 111052 54010 7544 43524 6414 93020 81451 90262 65947 86220 34831 11736 54471 103491 42146 26136 11584 28666 50699 22506 114316 26350 106262 53089 31102 8196...
output:
1 3 5 9 4 6 10 18 34 66 85 123 127 255 143 279 559 1007 1535 2559 5023 9375 18655 35167 70335 79039 40031 21599 42079 84063 168127 168831 177919 341759 503295 1006591 1072127 1070079 1976319 2107391 1173503 2347007 4694015 4800511 9601023 18022399 9011199 17563647 34078719 65011711 129564671 1349386...
result:
ok 48590 lines
Test #8:
score: 0
Accepted
time: 374ms
memory: 80908kb
input:
131071 39479 96391 14017 23321 50455 14012 126360 118197 113346 92912 48354 86690 78318 34265 94323 55989 30079 44311 2276 30025 16215 90233 34881 85139 57791 13323 50082 125534 36843 69732 104952 39061 82716 2282 63268 42779 35368 9502 17575 123815 2726 43663 123675 93945 4192 64707 87905 123819 40...
output:
1 3 7 11 23 47 95 111 191 159 319 159 319 321 449 705 1409 2817 1409 2817 2945 5761 11521 11649 23297 46593 62979 96771 96775 190983 381959 762887 1295367 1295623 1296139 2574091 1287051 1549579 2606859 4721419 8950543 17896975 35793935 35810319 71604247 142661655 285274135 570515495 140973600 20810...
result:
ok 48889 lines
Test #9:
score: 0
Accepted
time: 483ms
memory: 138640kb
input:
200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
1 3 5 6 10 20 25 41 35 67 68 133 137 269 295 347 178 340 436 836 1636 882 1636 3236 6212 8580 4356 8580 16648 16652 32780 65036 65040 65052 99364 197668 391204 391348 395445 395509 329941 325844 594140 602352 602344 602896 603184 1148592 2279408 4507632 8964976 17878384 35706480 69575344 139043504 2...
result:
ok 50000 lines
Test #10:
score: 0
Accepted
time: 500ms
memory: 138760kb
input:
200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
1 0 1 0 1 3 5 6 9 17 29 53 105 109 219 359 719 687 815 1471 767 799 1567 2815 2819 3395 5895 11015 6407 4099 7747 12099 7747 15043 15299 7811 8067 15427 30467 30483 47891 47923 94515 48051 82915 163811 162675 299939 598947 601155 601027 598883 1173155 2246435 2213667 4327459 8620099 8883779 9411139 ...
result:
ok 50000 lines
Test #11:
score: 0
Accepted
time: 469ms
memory: 138688kb
input:
200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
1 3 4 8 17 33 35 69 71 103 199 391 777 1545 2573 4629 4645 4677 5205 9813 9849 19065 37529 38073 71913 74057 78345 149065 289737 306249 597065 1185097 2340169 4663881 9309769 18601033 18633865 37218441 74387593 74388617 147846281 164639881 299873417 299881609 570361105 111320074 193238035 384761861 ...
result:
ok 50000 lines
Test #12:
score: 0
Accepted
time: 390ms
memory: 140588kb
input:
200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911 73741816 147483633 294967267 589934535 179869064 359738129 719476259 438952512 877905025 755810044 511620082 23240158 4648031...
result:
ok 50000 lines
Test #13:
score: 0
Accepted
time: 5ms
memory: 11840kb
input:
2 2 1 1 + 1 2
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 484ms
memory: 139448kb
input:
199995 155591 84519 61935 30297 10507 50670 31433 44852 51946 66366 19875 139938 49384 32594 37301 47996 34365 183321 76049 140453 161840 35668 98447 31470 121808 178617 152466 151593 65823 32363 93866 105853 46225 52952 73205 104232 53556 117961 116263 25709 35865 154071 103869 165665 12601 69007 1...
output:
1 3 7 15 31 63 127 63 65 69 133 201 393 785 1313 2369 4737 9347 18691 22787 23299 14723 29447 58887 116231 232455 232457 464907 929803 931851 1863691 1863707 3727387 7405611 5300267 10543147 21037099 21069899 42139723 84181067 84541579 168427667 302842003 370409619 370934035 370934037 370934039 6397...
result:
ok 49974 lines
Test #15:
score: 0
Accepted
time: 517ms
memory: 139408kb
input:
199905 79361 22628 85515 176871 42721 191047 19249 155911 174279 46395 89532 15935 22410 160311 77636 113388 37333 126483 89841 84166 81187 156956 40438 134742 88864 75960 167049 165084 148066 131259 163069 33947 108538 183436 58206 114505 6039 107228 144690 57925 70292 99711 71839 5183 160709 17106...
output:
1 3 7 15 17 33 67 135 271 135 263 519 1031 2063 4127 8223 16447 32831 65663 65665 131329 262657 262659 524803 1049603 2099203 4198403 8392707 16785411 16801795 33603589 67158021 67223557 67354631 134709255 268926983 537853959 75707904 151415801 298899435 597798863 597815247 187749776 367618841 72735...
result:
ok 50000 lines
Test #16:
score: 0
Accepted
time: 549ms
memory: 139148kb
input:
199939 126810 92434 174421 81735 162986 75711 26318 69965 44031 54588 52970 162790 176803 66069 198642 123421 112371 59917 69715 154951 112429 126181 124836 44060 161984 166636 176647 8286 48943 12663 45982 17218 107525 135492 109734 176034 55893 78212 149096 174588 185790 97850 53570 115245 15674 5...
output:
1 2 5 9 19 23 43 79 151 287 367 639 799 815 1599 3007 2975 3007 5855 5919 11743 20159 20415 37503 42111 21503 39551 21503 40447 38271 20415 10943 20607 20863 20927 40383 40415 78335 153087 290431 290435 293507 578435 575363 574275 1144163 574819 579175 1140327 599399 616807 1206663 2386567 4543111 4...
result:
ok 49970 lines
Test #17:
score: 0
Accepted
time: 523ms
memory: 139396kb
input:
200000 134020 173608 13619 76918 17133 29513 146404 65973 109441 86709 190753 99348 120252 193475 124549 88478 91223 161633 137027 31976 172490 172145 94014 44903 129191 110979 199230 122293 82006 195511 76950 113837 180737 110162 18584 54568 62651 3416 51537 146087 100876 161613 4553 82514 187084 6...
output:
1 3 7 11 12 20 28 32 61 101 165 325 647 1163 2191 4367 8471 16919 33311 66591 133167 266287 528447 528575 1056991 2109791 4219231 8438111 16875871 33751455 33882527 34144671 68288959 69337535 138674879 142869183 285738175 571475199 142950136 142950138 216692211 364176101 431284965 431285093 72625466...
result:
ok 50000 lines
Test #18:
score: 0
Accepted
time: 371ms
memory: 62544kb
input:
199991 131115 127761 128141 9947 118948 199136 194495 52407 3038 150618 109068 296 118921 42906 32966 194326 18727 155009 153415 91730 183299 123049 77426 36132 60131 170134 192268 118595 53024 145284 74390 135856 90091 97771 170069 46155 78532 83748 76184 115369 196830 14441 83234 137528 118706 114...
output:
1 2 4 6 12 20 41 73 145 225 259 267 535 1055 1057 1969 2241 2785 2849 3105 6211 6275 8323 13699 18307 32131 59971 116675 171139 330883 355459 710147 1365507 2708995 2758147 2958851 5776899 11019779 21636611 43198727 86388495 172768015 178017055 196638239 213427775 280561215 560531007 594134591 59441...
result:
ok 49942 lines
Test #19:
score: 0
Accepted
time: 370ms
memory: 59448kb
input:
199921 88253 52631 43472 60168 126943 91568 42376 149650 182742 18220 189063 55458 1983 73802 43527 24362 15388 94498 60070 26890 156887 181370 13959 3538 8673 116293 172414 98912 75585 182988 56402 69400 116203 63483 168182 89766 140594 83130 62023 108013 131617 127308 111490 181754 146979 16032 14...
output:
1 3 5 2 3 6 12 6 10 14 13 21 13 21 35 71 143 287 415 575 1151 575 639 959 963 1923 2563 5123 8707 16899 20995 37891 38019 38275 43395 33155 57091 114179 118275 132103 132105 69641 81929 163849 186385 364577 729153 1441921 1802497 3293441 3817729 7635201 7635715 15271171 16581891 20776195 41551107 82...
result:
ok 49969 lines
Test #20:
score: 0
Accepted
time: 376ms
memory: 61676kb
input:
199961 6566 6320 120135 64612 120403 93339 9289 16098 118401 47489 14946 175740 51984 17767 160551 69679 80762 39816 74519 115327 180551 154037 67164 153772 175897 137890 74592 16932 6311 83607 87740 12379 68295 123078 8740 48267 58674 29448 42492 199128 113955 68509 192499 185731 158313 61660 24163...
output:
1 2 5 11 23 47 95 97 101 197 391 197 389 517 1033 1545 1561 3121 6209 12355 12363 20555 24651 49291 98519 196951 393559 786775 983383 786775 788823 1575263 1576031 2103391 4206719 6836351 13652159 22061247 44122463 44122527 44147167 88294175 88326943 155435807 289800991 290456479 290456991 307234719...
result:
ok 49937 lines
Test #21:
score: 0
Accepted
time: 399ms
memory: 60324kb
input:
199986 197271 19652 144685 60421 178455 136710 192878 14024 116174 39504 89189 150440 111847 47085 137023 135177 49593 188587 99891 165060 17432 133195 154398 95839 144244 77014 69862 91980 825 164367 111143 35742 180176 93478 11627 19622 189240 74023 190299 5562 197105 11166 187214 86304 76464 7135...
output:
1 0 1 2 5 11 13 7 11 13 14 26 44 76 148 276 536 1056 2096 2624 5216 10336 20608 41216 41856 82817 82881 82913 85185 42593 21985 39393 78785 39617 39635 76755 77139 39051 77195 150923 299275 299283 299275 365331 497699 991811 992835 995907 1525895 769607 1034183 2067399 4133831 8259399 12552007 21006...
result:
ok 49976 lines
Test #22:
score: 0
Accepted
time: 436ms
memory: 101224kb
input:
199948 127561 156846 73803 21852 177891 61198 173157 58416 53953 155974 172123 176895 131223 39360 42579 13568 76543 165055 60377 9906 29609 74224 91670 35997 145883 152903 87501 87785 20937 160730 83347 21491 51113 8163 147789 36552 150228 133873 171328 56242 19348 43247 191703 65970 9398 21934 913...
output:
1 0 1 3 5 6 11 19 39 47 59 119 135 199 263 527 399 495 927 1503 1759 2655 4703 7263 12991 13119 13375 13503 15807 27775 54911 102015 200831 106623 172159 189567 190079 206463 209279 214911 249727 319871 460159 660863 666111 1299199 2562303 3741951 4987135 5642495 11264255 22528511 28336639 46096895 ...
result:
ok 50000 lines
Test #23:
score: 0
Accepted
time: 412ms
memory: 99852kb
input:
200000 19501 72549 169108 68861 17653 94137 54534 18997 89426 140431 65005 45936 113520 161951 134524 74528 144019 85516 107071 102714 5262 143555 53739 24459 88014 114776 175394 81037 193370 162716 100826 143166 3700 134554 195547 29822 120283 155023 114520 164141 23561 189321 26049 175925 179016 1...
output:
1 2 4 6 10 18 34 66 130 258 386 453 837 903 1671 1703 871 1671 1673 2825 5513 10761 21001 41737 41735 43271 86279 45191 45319 82311 45319 86471 156295 303751 305799 306183 318471 159623 318471 615687 1161223 2235919 2236431 4406799 4439567 4431375 8855567 17447951 34883599 35411983 70293519 14055015...
result:
ok 49924 lines
Test #24:
score: 0
Accepted
time: 16ms
memory: 11876kb
input:
2 2 1 50000 + 1 1 + 1 2 + 1 2 + 1 1 + 1 1 + 2 2 + 2 2 + 1 1 + 1 1 + 1 2 + 2 2 + 2 2 + 2 2 + 2 2 + 1 2 + 1 1 + 1 1 + 2 2 + 2 2 + 1 1 + 1 2 + 2 2 + 1 2 + 2 2 + 2 2 + 1 1 + 1 1 + 1 1 + 1 2 + 2 2 + 1 1 + 2 2 + 2 2 + 1 1 + 1 1 + 2 2 + 1 1 + 1 1 + 2 2 + 1 1 + 1 2 + 1 2 + 1 2 + 1 2 + 2 2 + 2 2 + 1 1 + 1 2 ...
output:
1 3 7 15 31 35 43 75 139 279 311 375 503 759 1519 2031 3055 4079 6127 8175 16351 24543 49087 81855 147391 163775 196543 262079 524159 786303 1048447 1572735 2621311 3145599 4194175 6291327 8388479 12582783 16777087 25165695 50331391 100662783 201325567 402651135 536868863 805304319 73739768 14747953...
result:
ok 50000 lines
Test #25:
score: 0
Accepted
time: 480ms
memory: 99108kb
input:
200000 64610 125539 83705 160281 24143 45832 154846 82764 60201 126231 119699 193755 189389 133775 113877 66009 85942 34335 130076 68332 135113 173609 92701 826 135328 9849 158095 38763 138070 81324 25151 1224 88250 90383 134197 157835 145476 119887 175766 9372 132312 98062 170675 17587 184233 4903 ...
output:
1 3 7 15 31 63 65 97 193 385 771 1539 3075 6151 12295 12311 12831 25135 50271 100543 100547 166083 331971 594243 595331 1185155 1185923 2235523 2497671 3026055 6050055 12098823 24157455 32583199 49434143 83136063 150244991 300191359 600087167 600104063 200190584 400368753 800737379 836720739 3736162...
result:
ok 49929 lines
Test #26:
score: 0
Accepted
time: 457ms
memory: 100264kb
input:
199969 167304 65417 4311 181236 168173 129988 105106 128180 25290 30357 7391 59851 8202 72186 141573 66876 150397 116010 136062 97012 30955 90714 27290 141690 143297 162143 82579 166833 187616 136103 177381 83739 140598 45445 33843 8765 193191 174188 164333 23706 134079 52023 55225 91918 168596 1867...
output:
1 3 5 7 15 17 25 35 55 111 191 383 463 927 1567 1695 3295 3391 6591 12671 12927 25727 48383 81151 161279 166911 303103 565247 565263 585743 586255 1164815 2321935 2322447 2326543 4464655 4474895 4491279 8767503 17534991 34967567 69177359 137596943 137961487 274276367 548413455 96556552 98653704 1112...
result:
ok 49967 lines
Test #27:
score: 0
Accepted
time: 506ms
memory: 107096kb
input:
200000 53698 117933 66256 173974 155051 150222 108377 88097 165733 1460 176632 22651 42045 84602 193837 42609 189747 21700 7674 93722 157742 75794 157398 119145 35104 140853 45711 84645 101278 149018 95798 58880 19405 131388 87737 182668 45503 140827 167401 151705 91293 118960 105734 52467 125430 75...
output:
1 3 1 2 4 3 7 9 17 25 41 57 99 131 195 291 583 967 1095 2191 2207 4399 4415 7295 4479 4991 7615 14015 22719 42175 37055 74111 148095 296063 582783 1148031 1279103 1623167 1623295 1656063 2245887 4490495 7898367 9242879 14485759 14493951 15018239 30036479 51024383 51188223 68620799 137241599 27394969...
result:
ok 49943 lines
Test #28:
score: 0
Accepted
time: 472ms
memory: 105324kb
input:
199922 107081 79120 3676 185326 84060 150979 197391 148825 189047 157345 59445 149477 184275 4094 66094 114629 90477 122338 34376 64548 124221 130428 122691 32881 145351 17012 35790 43743 35700 70460 96449 183837 187269 66576 93210 109210 55440 22006 85227 161356 156550 113505 139755 167518 165789 1...
output:
1 3 4 7 13 19 31 19 27 43 59 30 16 31 23 47 87 159 239 471 935 1479 2119 1095 2063 1487 1999 2127 2383 1767 1127 1255 627 755 1203 1335 1591 2535 3303 5639 11279 12303 14351 18447 27663 27679 32799 30751 30815 35263 22335 26623 30719 40063 50303 45695 66175 84863 89983 140159 238463 445823 298367 56...
result:
ok 49990 lines
Test #29:
score: 0
Accepted
time: 457ms
memory: 105008kb
input:
199922 154220 140933 123431 133706 26777 50582 193300 129242 144707 165894 198153 71220 138592 59306 194778 74897 3051 8956 50172 40039 106595 170361 146340 13971 26317 53384 90606 41548 132248 111371 103695 57445 194912 154378 111159 163942 31276 147729 44800 125401 20411 110815 196588 147245 10419...
output:
1 2 4 8 12 20 28 44 60 96 168 296 352 513 737 993 1985 3009 3521 3651 5699 11395 22787 28931 34051 68099 49921 31617 63233 93953 179713 295937 591873 600065 1067009 1935361 3672067 3803139 3803267 6228099 6500483 12726403 13381763 24785027 35008643 69873799 68563079 136982663 273318023 546472071 580...
result:
ok 49957 lines
Test #30:
score: 0
Accepted
time: 502ms
memory: 105508kb
input:
199979 78458 23155 161327 25592 128257 4920 165216 192902 190394 146360 10360 19392 20231 109640 25732 182433 110587 179405 86699 57912 157258 9243 96750 189064 81731 35609 165166 90771 41005 185425 166909 116598 116860 133728 187967 62078 13434 73265 87845 132491 90599 129409 97983 103399 69540 664...
output:
1 3 7 15 31 63 31 39 71 143 287 543 1087 1599 1727 3455 6911 3839 6655 12287 12295 12807 25095 25127 25191 25255 50343 100519 200967 352719 696783 836047 524719 836031 869183 870207 1738591 3475295 6752095 13504095 15601311 30805791 30806047 30805791 61214495 122032159 122560031 123615775 247231007 ...
result:
ok 50000 lines
Test #31:
score: 0
Accepted
time: 495ms
memory: 123348kb
input:
200000 131423 92760 144402 47110 39734 6689 113356 123141 94650 120955 79281 168150 95682 154312 3290 130359 47546 182644 148146 17629 178901 135802 101595 76730 124702 63138 11470 106580 31734 21610 43452 20380 145832 151393 67738 190285 37182 189589 105959 134078 149602 74747 165741 79730 155266 8...
output:
1 2 4 8 16 18 20 24 40 72 76 140 73 77 73 147 283 411 561 1109 2197 4385 2192 2224 2226 4446 8546 9570 18797 19309 19461 38683 41243 82247 123295 164495 164479 82495 164511 328479 492319 984639 1837823 1971327 2102399 2757759 3680127 5654911 11291391 11290367 11293439 14439167 14439679 28876031 3202...
result:
ok 49976 lines
Test #32:
score: 0
Accepted
time: 504ms
memory: 122696kb
input:
200000 93464 176045 35518 125153 178434 38114 132184 185778 138111 30626 150503 191059 191184 126041 98518 128645 185091 155423 88828 130498 28065 177253 12397 122082 33021 132204 113560 51911 62776 64391 103313 174046 41285 6885 73434 56983 100699 178816 159437 80569 146821 188970 179065 53580 1070...
output:
1 3 7 9 15 23 39 71 127 239 479 927 991 1343 2687 4479 5887 11775 12799 15871 31743 63487 118783 135167 167935 167951 282639 565279 1130527 2146367 2080831 3113023 6226047 12255359 11108479 15827071 15827583 24216191 43090559 86180479 168166527 84083327 119734911 239469823 240126207 261097727 420481...
result:
ok 49916 lines
Test #33:
score: 0
Accepted
time: 511ms
memory: 122312kb
input:
200000 58750 185410 102499 110634 157771 194113 93740 63560 90366 11239 198691 196889 90901 16916 137845 146488 41199 120635 107218 175350 86566 16202 190752 112622 19630 149425 20809 50491 83186 93216 32204 66173 89850 33837 91609 13682 63745 5595 160462 51463 166180 191879 181359 30627 143093 1557...
output:
1 3 1 2 4 6 11 13 9 13 15 19 33 37 59 67 83 85 93 135 219 387 419 787 1403 2555 4881 9469 10173 10181 19653 39005 39037 74157 140205 148397 292845 309229 577389 634733 1257325 2316403 4436087 8826999 17634519 17700247 35382679 68954535 136882599 273658671 545895215 91681848 91814456 92342840 9234079...
result:
ok 49964 lines
Test #34:
score: 0
Accepted
time: 519ms
memory: 122008kb
input:
200000 133666 168679 119112 127822 83847 102279 78104 73830 88051 106192 151217 46601 123049 96277 151021 47059 22496 48383 100550 36087 48839 72744 93083 27609 112788 123096 157340 16616 147625 171999 53910 103999 165616 32155 78086 121124 87174 3190 97858 121272 107801 185540 131287 187431 159750 ...
output:
1 2 4 3 5 11 23 47 55 71 119 183 215 375 439 279 551 1095 839 423 743 747 748 1396 2692 2820 5480 9712 10256 10768 10832 10864 20096 22144 44032 77857 77889 155201 310017 605377 1195329 2384001 2385153 1336449 2672769 2689665 1378881 2460289 2727809 4890625 9768961 18477313 36954113 18489345 1965260...
result:
ok 50000 lines
Test #35:
score: 0
Accepted
time: 19ms
memory: 11684kb
input:
3 3 2 1 3 50000 + 2 3 + 3 3 + 1 2 + 1 1 + 3 3 + 3 3 + 1 1 + 1 3 + 2 2 + 3 3 + 1 2 + 2 2 + 1 2 + 2 2 + 2 2 + 1 2 + 1 2 + 2 3 + 1 3 + 3 3 + 2 2 + 1 3 + 3 3 + 1 3 + 2 2 + 1 2 + 2 2 + 3 3 + 1 3 + 1 2 + 3 3 + 2 2 + 1 2 + 2 3 + 1 3 + 1 1 + 3 3 + 3 3 + 3 3 + 1 3 + 2 3 + 1 3 + 2 2 + 2 2 + 1 1 + 1 3 + 2 3 + ...
output:
1 3 7 9 17 33 37 75 79 143 287 303 607 671 799 1599 3199 6207 10495 18687 20735 37503 70271 136575 140671 281343 297727 559871 1087231 2174463 4271615 4337151 8674303 17324031 34125823 34191359 67745791 134854655 269072383 537622527 75015672 148986865 150035441 152132593 152656881 301123555 60028103...
result:
ok 50000 lines
Test #36:
score: 0
Accepted
time: 504ms
memory: 123124kb
input:
199994 36840 95135 129865 112251 101798 187774 14361 37008 55756 143530 46420 10936 191075 30027 14790 111279 188509 131410 67632 158004 161290 95558 33354 184015 153434 28737 120715 156963 41475 67538 76849 165125 84528 133034 26887 147086 107379 167253 191021 176690 137738 15327 81712 85451 105632...
output:
1 3 7 9 13 17 19 39 59 75 147 151 219 267 531 723 1175 1239 1495 2271 2783 3823 7647 8031 14943 29823 47231 93311 113791 125055 146623 232703 432511 864767 1565439 2999295 5997567 5997695 11338879 13960831 27921663 54529279 109058559 159390207 301996543 317463039 384571903 769143295 769180159 511571...
result:
ok 49999 lines
Test #37:
score: 0
Accepted
time: 449ms
memory: 123540kb
input:
199986 44484 88033 170763 105703 12052 15210 190682 3734 145537 55731 26309 75415 9754 163115 120925 174031 143835 44064 108502 155133 124880 77386 35705 96348 13158 30865 198214 130710 112779 59176 133450 29375 173445 142656 145480 5526 195745 105013 191262 146057 102105 172477 5524 56587 187688 67...
output:
1 3 5 9 19 27 31 47 91 179 307 615 655 1311 1135 2271 2367 4607 5375 10239 18431 18943 18947 23043 11779 12419 6659 7171 7427 14211 24963 35331 57863 66567 87055 168991 175135 350239 579647 1159231 643135 1011775 1830975 3530815 3948607 7716927 13221951 26443839 51707967 52494399 52592703 52756543 1...
result:
ok 49935 lines
Test #38:
score: 0
Accepted
time: 521ms
memory: 124252kb
input:
199972 149584 42693 76362 49467 159038 49395 44882 74291 93306 101070 93733 115544 4575 75791 148735 72413 52295 152497 8417 85198 86901 57115 116032 36187 15637 102061 76801 49118 40864 111559 102517 58069 36985 58063 187123 152686 48022 2108 80569 82216 48854 12046 136801 144587 53750 117438 11649...
output:
1 3 5 9 5 2 5 11 12 24 40 72 145 153 179 359 679 711 879 1727 3263 2559 2567 4647 9295 9327 10831 21519 22031 44047 77071 80655 160783 161807 81415 94727 162567 324103 644615 777735 1554447 865807 865815 1390615 2780207 3238959 6474815 10882111 10886207 10894431 21787807 43574431 43558047 21930655 4...
result:
ok 50000 lines
Test #39:
score: 0
Accepted
time: 518ms
memory: 122996kb
input:
199960 66674 111218 60472 126836 112058 72024 53650 50961 133801 160785 104450 23301 199211 36411 142414 114723 127074 113631 10195 33573 102303 47087 31978 27788 155288 92753 102734 46245 197327 139719 93627 196008 190639 196187 171833 155974 97160 6948 13917 193576 166533 151078 70620 144489 68976...
output:
1 2 4 8 17 35 67 131 195 323 643 655 911 1823 1887 3775 7391 7407 14703 22895 23983 27215 27983 44367 47519 88479 92575 92703 180895 324511 324543 353215 706175 706687 837759 1624191 2854079 5050303 9508799 9510847 19017983 20329343 40653695 40720255 41836671 41836703 77750431 148021407 148022431 14...
result:
ok 49983 lines
Test #40:
score: 0
Accepted
time: 438ms
memory: 139264kb
input:
200000 163387 94400 130365 31392 174420 57560 103105 32878 96595 10564 90097 179557 162011 107745 193662 192972 80073 198975 24026 178154 14362 20437 15559 36902 155321 19505 81151 80049 192912 134867 155410 21396 21445 99997 46433 113144 10486 89572 85233 144920 120692 10151 37988 122772 90110 6969...
output:
1 2 4 2 4 3 7 3 1 3 7 3 7 15 31 15 31 15 7 3 1 0 1 0 1 3 1 3 7 11 23 39 71 87 55 39 79 39 19 23 17 21 43 75 139 183 215 183 367 735 1375 2399 2095 1071 2143 1119 1055 2079 4127 8255 16447 8255 8259 4163 8263 4163 2115 1059 2115 2147 4195 8295 8311 16519 18631 10419 10291 20563 12369 24659 12363 8267...
result:
ok 49994 lines
Test #41:
score: 0
Accepted
time: 322ms
memory: 60704kb
input:
199946 11967 40196 114587 61975 103751 60735 178039 109154 12518 59533 146422 133138 106386 38649 104155 126399 31899 50912 110951 183773 115832 118367 135065 20533 158350 63600 57717 44063 102917 95997 183849 42677 71877 148923 88305 154146 113193 153271 192551 53235 124542 21766 127440 107238 2281...
output:
1 2 1 2 3 2 1 3 5 9 4 3 1 3 1 3 1 0 1 3 5 9 17 35 43 87 119 191 159 303 559 1103 551 679 339 595 307 595 591 527 783 1567 1695 1823 911 913 923 939 475 499 255 159 183 323 427 811 619 603 365 717 365 461 923 1179 923 919 791 1583 1071 1903 1887 3743 3807 4031 4543 4547 4419 8835 4419 4259 4295 2167 ...
result:
ok 50000 lines
Test #42:
score: 0
Accepted
time: 371ms
memory: 99424kb
input:
200000 133972 109486 8068 182579 171264 91251 164605 12251 176542 79672 76644 83254 113978 154294 153753 134144 24328 64385 139999 13474 68006 154017 12511 40582 31107 36891 68316 131489 51534 61164 100735 109836 133530 159486 148250 38750 114387 163081 123918 21938 189321 126743 120406 173986 83822...
output:
1 3 1 3 1 2 5 6 4 3 1 0 1 2 1 0 1 2 1 0 1 0 1 0 1 0 1 3 7 15 31 39 23 39 19 11 19 11 19 21 19 27 29 57 89 179 211 105 115 155 307 387 515 403 369 739 643 387 195 231 191 175 183 91 73 69 37 33 17 15 7 15 17 9 11 23 43 44 34 44 28 18 17 33 67 35 71 39 55 71 135 67 35 43 75 77 85 77 85 53 41 69 39 77 ...
result:
ok 50000 lines
Test #43:
score: 0
Accepted
time: 413ms
memory: 105928kb
input:
200000 135285 86406 193685 187759 28813 126955 119609 188194 6960 136819 172807 154864 797 157733 7023 43617 66713 125717 107689 152403 28264 184813 5265 17027 174774 115075 153438 198251 119793 125620 123733 22993 166544 25623 4615 49051 68418 10418 84661 158854 158406 12775 178172 187097 198020 10...
output:
1 0 1 0 1 0 1 2 3 2 1 0 1 0 1 3 7 3 7 15 31 15 16 15 7 15 7 3 7 3 1 0 1 0 1 0 1 3 1 0 1 0 1 0 1 3 1 0 1 2 4 3 1 2 4 6 13 23 31 55 29 25 41 57 97 49 33 25 12 21 11 13 17 29 27 43 35 21 13 15 29 15 9 7 13 27 23 11 19 11 5 9 11 6 8 6 9 7 11 9 17 9 5 3 7 15 31 47 31 63 95 191 95 191 95 191 383 639 1279 ...
result:
ok 50000 lines
Test #44:
score: 0
Accepted
time: 434ms
memory: 122288kb
input:
199930 48074 80810 36504 118301 102740 194889 47992 57694 106856 55982 43440 69176 29678 49687 17641 83699 79431 129872 58616 52099 162746 123014 143502 130653 110321 40999 54066 25929 71458 8206 7442 144249 199397 15138 197497 43237 28469 7986 69517 187498 20654 129661 173261 198769 142327 61670 14...
output:
1 3 7 9 19 39 79 159 319 255 127 63 127 63 31 15 7 15 7 3 7 11 15 19 15 31 47 35 67 71 139 271 263 135 263 135 271 335 463 231 295 195 323 343 183 359 719 1439 2847 3103 5951 3519 4287 3263 3135 6207 6463 5311 3775 2751 5375 7423 3775 4287 6847 4287 2175 1119 2175 3007 4799 3007 4031 6143 6399 6143 ...
result:
ok 50000 lines
Test #45:
score: 0
Accepted
time: 442ms
memory: 123712kb
input:
200000 122932 140125 129341 182866 46556 79821 170528 55257 53720 51334 19830 45347 92313 113207 64552 158918 134182 155406 178215 136008 186506 49934 51621 135241 2637 110247 14678 115257 99908 9909 8606 28054 32110 192058 18184 2997 150768 37295 105940 79278 37717 169431 68087 89059 134829 85959 2...
output:
1 0 1 2 1 0 1 0 1 3 1 0 1 0 1 0 1 0 1 2 1 2 1 0 1 2 1 0 1 0 1 0 1 0 1 3 7 11 7 11 5 3 1 3 1 3 4 3 1 3 1 3 1 0 1 2 1 3 7 3 1 2 4 3 7 11 5 11 7 3 1 0 1 0 1 0 1 3 1 0 1 0 1 0 1 0 1 0 1 3 7 9 13 14 10 6 5 3 5 3 5 3 5 11 19 11 5 2 1 3 1 3 7 9 5 2 1 0 1 0 1 2 1 0 1 0 1 0 1 0 1 3 7 15 19 9 5 2 4 2 1 2 1 0 ...
result:
ok 49996 lines
Test #46:
score: 0
Accepted
time: 17ms
memory: 11756kb
input:
4 4 1 1 3 2 1 50000 + 2 3 + 4 4 + 4 4 + 1 4 + 1 4 + 2 3 + 1 3 + 1 3 + 3 4 + 1 3 + 1 4 + 1 1 + 2 4 + 2 4 + 1 2 + 1 3 + 1 4 + 2 4 + 3 3 + 2 2 + 1 2 + 3 3 + 2 2 + 1 3 + 2 4 + 2 3 + 2 2 + 2 3 + 3 3 + 1 3 + 1 3 + 1 3 + 2 2 + 1 4 + 2 3 + 1 3 + 3 4 + 2 2 + 2 4 + 4 4 + 1 3 + 1 4 + 4 4 + 1 2 + 3 4 + 3 3 + 2 ...
output:
1 2 4 9 19 27 43 75 151 279 559 1071 2143 4287 8383 16575 33151 66303 66431 66495 132095 132351 132607 264063 527359 1053183 1055231 2108927 2113023 4217343 8425983 16843263 16851455 33630207 67257343 134480895 268931071 268963839 537468927 537485311 74814968 148585457 148650993 296261603 592269255 ...
result:
ok 50000 lines
Test #47:
score: 0
Accepted
time: 441ms
memory: 123576kb
input:
200000 189404 73188 94395 54404 11733 110279 181147 41399 11204 163094 64526 16888 136513 198440 183267 194176 6950 25635 175375 64342 189554 144823 164155 8485 102824 82381 130681 50110 193807 161933 116079 172036 78548 185573 65460 8842 179536 112172 47040 97785 112638 168042 103138 142049 118536 ...
output:
1 0 1 0 1 0 1 0 1 0 1 0 1 3 1 3 1 3 1 0 1 0 1 3 7 11 19 31 15 23 15 7 8 17 8 5 3 2 1 2 3 2 1 0 1 2 5 9 17 15 7 3 1 3 1 2 5 3 1 0 1 0 1 0 1 2 4 2 3 6 7 5 3 5 3 2 4 6 7 12 8 15 23 31 61 45 73 123 107 59 31 27 43 87 167 159 319 191 223 127 63 95 175 239 351 175 335 351 255 479 239 119 85 165 173 333 66...
result:
ok 50000 lines
Test #48:
score: 0
Accepted
time: 509ms
memory: 139160kb
input:
200000 77504 150136 149029 100126 79630 152786 59741 36581 142342 154069 197187 16668 54154 180361 115847 164757 122071 198863 65801 149813 11733 120875 44374 112671 21400 138274 143662 21212 191706 63110 6236 152126 99016 97732 79026 187141 117803 84677 99898 30517 89769 102382 55638 20267 11434 13...
output:
1 3 7 11 19 35 71 143 271 543 1087 2111 4159 8319 8327 16655 17167 22031 44047 76831 142367 284703 323615 647231 1294463 2588799 4685951 9371775 10616959 11141247 14155903 14157951 20187263 24383615 32772223 65544319 131080447 164634879 329269759 463487487 926974975 463878648 927691761 464564714 612...
result:
ok 50000 lines
Test #49:
score: 0
Accepted
time: 351ms
memory: 60428kb
input:
200000 122019 98771 118577 111790 106704 118678 177418 168810 194976 164789 31289 199544 70813 177000 58395 124876 77214 93965 19556 80774 61898 147269 105655 131685 83150 89692 175727 112770 116783 56312 189933 71031 120984 31638 140197 108867 55097 33350 32179 138234 127312 52428 71319 44011 15327...
output:
1 3 7 15 31 63 127 143 287 575 577 1089 1093 2185 2441 2953 5907 6163 6291 6547 7571 15123 29731 49699 77379 154691 161859 321667 321795 641411 641475 645703 907847 1776199 3552399 7104655 14208159 27628703 28255423 56509695 56510719 59001087 113004927 117199231 229400959 279732607 281829759 3874737...
result:
ok 50000 lines
Test #50:
score: 0
Accepted
time: 446ms
memory: 105612kb
input:
200000 86460 127915 164559 85215 88871 130138 133323 175625 106579 168398 79795 62863 1092 71833 180868 185053 169498 190742 135255 45630 59395 58051 115559 194976 143570 36656 144275 195207 187593 44810 136612 188073 61988 64547 154433 102694 112338 111870 15258 70873 30817 63402 60800 94273 14553 ...
output:
1 2 3 7 9 17 29 45 47 89 179 207 407 807 935 1775 1776 2256 2304 4288 7872 8705 8833 14017 25409 45889 46401 58689 111937 223873 446593 450689 712833 1423489 2242689 2242817 4483585 8894977 17746433 35449345 36776961 38917121 64082945 66737153 66741249 128697345 252609537 282305537 283108353 3600476...
result:
ok 50000 lines
Test #51:
score: 0
Accepted
time: 460ms
memory: 122300kb
input:
200000 167885 110 170987 33868 121388 141172 112843 4047 47096 178346 192149 74520 163904 148077 42019 197927 187109 154268 134330 152148 122580 93323 94026 74679 91129 49079 14924 132590 190679 138438 20678 76905 93943 186082 115515 181230 42418 98010 63147 166362 48174 26646 42722 66007 96659 2245...
output:
1 2 4 9 17 19 23 25 45 61 93 187 255 383 415 823 1607 2631 5231 5359 6063 6111 8543 10079 14175 16559 16703 32703 49727 97119 98655 194911 266079 267167 406431 409119 445983 474943 696127 696383 1392191 2014783 4014143 6832191 11682943 15761023 31518335 63033983 125948543 130142847 130143359 1994312...
result:
ok 50000 lines
Test #52:
score: 0
Accepted
time: 471ms
memory: 122956kb
input:
200000 119333 139147 130394 5613 35775 148679 130904 46270 28230 107747 5969 57625 177449 30191 49545 196340 119443 79272 4198 107975 98434 179900 167689 31071 175918 32664 130997 78379 111386 149604 193645 48716 174280 144964 66719 127197 97462 66002 30848 156592 161511 185455 109297 186651 53080 5...
output:
1 2 4 7 8 14 16 26 42 52 60 116 189 205 411 787 1331 1603 3107 6179 12227 13379 13639 27271 31495 62991 119311 120335 121359 126991 183311 193551 275471 341007 519183 1022991 2030607 3017743 5884943 11769887 11770399 19241503 19249695 19282463 38384159 64254495 64385567 64385631 64388287 110459263 2...
result:
ok 50000 lines
Test #53:
score: 0
Accepted
time: 24ms
memory: 11788kb
input:
4 3 1 2 1 2 4 50000 + 1 4 + 1 2 + 2 2 - 1 4 - 2 2 + 1 1 - 1 1 + 1 1 - 1 2 + 3 3 + 1 1 + 4 4 - 4 4 + 1 2 + 3 4 + 3 4 + 2 2 + 2 2 + 1 3 + 2 4 + 2 4 + 3 3 + 4 4 - 2 4 + 2 2 + 4 4 - 2 2 + 1 3 + 1 3 + 1 4 + 2 4 - 3 3 + 3 4 + 2 3 + 2 2 + 3 4 + 3 4 + 1 3 + 1 3 + 1 2 + 2 3 + 2 4 + 1 4 - 1 1 + 1 3 + 1 3 + 1 ...
output:
1 3 7 3 1 3 1 3 1 2 4 5 4 8 17 35 43 59 95 127 191 207 223 151 215 231 167 255 431 767 943 879 1759 3327 4351 8703 17407 26111 43519 84223 167679 201215 398335 267263 402431 672767 1197055 598527 1122815 2237439 2371583 2387967 4509695 4777983 9506815 9539583 10645503 10776575 11038719 11563007 1051...
result:
ok 50000 lines
Test #54:
score: 0
Accepted
time: 4ms
memory: 12416kb
input:
1000 547 681 16 241 623 782 14 286 855 917 613 756 854 333 84 40 343 353 63 106 180 482 768 578 299 180 582 238 998 699 766 455 114 282 206 786 151 844 841 317 409 705 560 387 872 441 290 501 457 954 36 807 267 167 608 99 244 857 696 787 56 452 327 735 684 125 193 772 308 237 180 923 735 701 236 599...
output:
1 3 7 15 16 32 16 32 16 8 7 15 31 63 31 15 7 3 1 2 4 6 5 9 17 35 19 35 67 131 195 323 643 1159 2183 4359 8711 8839 9871 10399 20127 24735 48287 95391 95647 95391 186655 322079 584735 1168447 635455 1168447 1168455 2218055 4333639 8630407 17248391 34095239 34357383 34373767 68321415 136609927 2731952...
result:
ok 1000 lines
Test #55:
score: 0
Accepted
time: 71ms
memory: 60968kb
input:
200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911 73741816 147483633 294967267 589934535 179869064 359738129 719476259 438952512 877905025 755810044 511620082 23240158 4648031...
result:
ok 5274 lines
Test #56:
score: 0
Accepted
time: 311ms
memory: 90676kb
input:
131072 105377 37060 95043 77702 24584 127218 26744 64395 66155 38930 60080 31888 30279 4795 87959 39534 84508 1854 114595 28824 2809 19036 94900 54211 54180 13413 5652 99859 104245 100479 14170 79895 118224 7206 62548 125572 81252 48406 120877 84357 85666 66171 23230 2186 38143 6930 2400 4937 99863 ...
output:
1 2 5 11 23 25 49 81 163 323 387 388 420 676 677 673 1345 2369 4545 9089 18049 35969 71937 137473 137985 275969 550402 1100802 2149378 4298754 4370436 4370500 8728648 17444944 17449040 34898000 18120752 18120768 36216896 18128952 9064504 9080888 9080890 17477722 34271386 67858586 135651482 271180066...
result:
ok 45080 lines
Extra Test:
score: 0
Extra Test Passed