//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
const int maxn = 4e4 + 5;
string tafrigh(string a, string b)
{
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while(a.size() > 1&& a[a.size() - 1] == '0')
a.pop_back();
while(b.size() > 1&& b[b.size() - 1] == '0')
b.pop_back();
int B = b.size(), A = a.size();
while(B ++ < A)
b.pb('0');
int now = 0;
//cout << a.size() << " " << b.size() << '\n';
//return a;
for(int i = 0; i < (int)b.size(); i++)
{
int x = b[i] - '0' + now;
now = 0;
while(a[i] - '0' < x)
{
a[i] += 10;
now += 10;
}
a[i] -= x;
/*if(a[i] >= b[i])
a[i] -= (b[i] - '0');
else
{
a[i] += 10;
a[i] -= (b[i] - '0');
now += 10;
}
if(a[i] - '0' >= now)
{
a[i] -= now;
now = 0;
}
else
{
a[i] += 10;
a[i] -= now;
now = 10;
}*/
now /= 10;
}
a.pb('0');
//cout << a << " " << b << '\n';
while(a.size() > 1&& a[a.size() - 1] == '0')
a.pop_back();
reverse(a.begin(), a.end());
return a;
}
string jam(string a, string b)
{
if(a.size() < b.size())
swap(a, b);
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while(a.size() > 1&& a[a.size() - 1] == '0')
a.pop_back();
while(b.size() > 1&& b[b.size() - 1] == '0')
b.pop_back();
int B = b.size(), A = a.size();
while(B ++ < A)
b.pb('0');
int now = 0;
//cout << a.size() << " " << b.size() << '\n';
//return a;
for(int i = 0; i < (int)b.size(); i++)
{
int x = a[i] - '0' + b[i] - '0' + now;
a[i] = x % 10 + '0';
now = x / 10;
}
a.pb(now + '0');
a.pb('0');
//cout << a << " " << b << '\n';
while(a.size() > 1&& a[a.size() - 1] == '0')
a.pop_back();
reverse(a.begin(), a.end());
return a;
}
bool is2(string a, string b)
{
reverse(a.begin(), a.end());
//reverse(b.begin(), b.end());
while(a.size() > 1&& a[a.size() - 1] == '0')
a.pop_back();
/*while(b.size() > 1&& b[b.size() - 1] == '0')
b.pop_back();*/
int now = 1;
for(int i = 0; i < (int)a.size(); i++)
{
int x = a[i] - '0';
x *= 2;
x += now;
now = x / 10;
a[i] = x % 10 + '0';
}
a.pb(now + '0');
while(a.size() > 1&& a[a.size() - 1] == '0')
a.pop_back();
/*while(b.size() > 1&& b[b.size() - 1] == '0')
b.pop_back();*/
//reverse(b.begin(), b.end());
reverse(a.begin(), a.end());
//cout << a << '\n';
return (a == b);
}
int n, par[maxn], num[maxn], par2[maxn];
string a[maxn], last, o = "1";
bool use[maxn];
int getpar2(int v)
{
return (v == par2[v] ? v : par2[v] = getpar2(par2[v]));
}
int getpar(int v)
{
return (v == par[v] ? v : par[v] = getpar(par[v]));
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
/*srand(time(0));
int level = 1000000;
while(level --)
{
int x = rand() % 1000;
int z = x * 2 + 1;
//int d = x - y;
//cout << x - y << " ";
string X, Y, o = "1", Z;
while(x)
{
X.pb(x % 10 + '0');
x /= 10;
}
while(z)
{
Z.pb(z % 10 + '0');
z /= 10;
}
reverse(X.begin(), X.end());
reverse(Z.begin(), Z.end());
//cout << X << " " << Y << '\n';
Y = X + X + o + Z - Z;
if(!is2(X, Y))
cout << X << " " << Y << '\n';
//cout << is2(X, Y) << '\n';
}
return 0;
string A = "15", B = "31";
cout << A - B << '\n';
cout << A + B << '\n';
cout << is2(A, B) << '\n';
cout << A << " " << B << '\n';
return 0;*/
//string last = a[1];
a[0] = "0";
cin >> n >> a[1];
for(int i = 2; i <= n; i++)
{
cin >> a[i];
//string tmp = a[i];
//a[i] = a[i] - last;
//last = tmp;
}
for(int i = 0; i < maxn; i++)
par[i] = par2[i] = i;
int mx = n;
//string now = "";
//int lst = 1;
set<int> st;
for(int i = 1; i <= n; i++)
if(jam(jam(a[i - 1], a[i - 1]), o) == a[i])
st.insert(i);
//cout << st.size() << '\n';
while(mx > 0&& st.size())
{
//int ptr = -1;
//for(int i = 1; i <= n; i++)
// cout << a[i] << " ";
//cout << '\n';
/*for(int i = getpar(lst); i <= n; i++)
{
if(use[i])
continue;
int p = getpar(i - 1);
//cout << i << " " << getpar(i - 1) << '\n';
if(use[p])
continue;
if(jam(jam(a[p], a[p]), o) == a[i])
{
ptr = i;
mi = tafrigh(a[i], a[p]);
}
}*/
//cout << ptr << '\n';
//cout << ptr << '\n';
//if(ptr == -1|| ptr == 0)
// break;
int ptr = *--st.end();
st.erase(ptr);
//continue;
//cout << ptr << '\n';
string mi;
//cout << a[ptr] << " " << a[getpar(ptr - 1)] << " " << mi << '\n';
mi = tafrigh(a[ptr], a[getpar(ptr - 1)]);
num[ptr] = mx --;
par[ptr] = getpar(ptr - 1);
par2[ptr] = getpar2(ptr + 1);
use[ptr] = 1;
//lst = getpar(ptr);
//a[ptr] = a[ptr] - a[getpar(ptr - 1)];
//cout << a[ptr] << '\n';
//cout << '\n';
for(int i = getpar2(ptr); i <= n;)
{
//cout << i << " " << a[i] << " " << mi << '\n';
st.erase(i);
a[i] = tafrigh(a[i], mi);
if(is2(a[getpar(i - 1)], a[i]))
st.insert(i);
//if(getpar2(i + 1) <= n&& jam(jam(a[i], a[i]), o) == a[getpar2(i + 1)])
// st.insert(getpar2(i + 1));
i = getpar2(i + 1);
//cout << i << " " << a[i] << '\n';
}
//cout << '\n';
//st.erase(ptr);
//a[ptr] = '0';
}
for(int i = 1; i <= n; i++)
{
//if(num[i] == 0)
// num[i] = mx --;
cout << num[i] << " ";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
91 ms |
2156 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
91 ms |
2156 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2028 KB |
Output is correct |
| 5 |
Execution timed out |
4059 ms |
11768 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
91 ms |
2156 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2028 KB |
Output is correct |
| 5 |
Execution timed out |
4059 ms |
11768 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
91 ms |
2156 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2028 KB |
Output is correct |
| 5 |
Execution timed out |
4059 ms |
11768 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
91 ms |
2156 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2028 KB |
Output is correct |
| 5 |
Execution timed out |
4059 ms |
11768 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
91 ms |
2156 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2028 KB |
Output is correct |
| 5 |
Execution timed out |
4059 ms |
11768 KB |
Time limit exceeded |
