//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("Ofast")
const int maxn = 7e4 + 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];
string a[maxn], last;
bool use[maxn];
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;*/
cin >> n >> a[1];
//string last = 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] = i;
}
int mx = n;
//string now = "";
while(mx > 0)
{
int ptr = -1;
//for(int i = 1; i <= n; i++)
// cout << a[i] << " ";
//cout << '\n';
string mi;
for(int i = 2; i <= n; i++)
{
if(use[i])
continue;
int p = getpar(i - 1);
//cout << i << " " << getpar(i - 1) << '\n';
if(!p|| use[p])
continue;
if(is2(a[p], a[i]))
{
ptr = i;
mi = tafrigh(a[i], a[p]);
}
/*else
cout << a[p] << " " << a[i] << '\n';*/
}
//cout << ptr << '\n';
//cout << ptr << '\n';
if(ptr == -1|| ptr == 0)
break;
num[ptr] = mx --;
par[ptr] = getpar(ptr - 1);
use[ptr] = 1;
//a[ptr] = a[ptr] - a[getpar(ptr - 1)];
//cout << a[ptr] << '\n';
//cout << '\n';
for(int i = ptr; i <= n; i++)
{
if(!use[i])
a[i] = tafrigh(a[i], mi);
//cout << i << " " << a[i] << '\n';
}
//a[ptr] = '0';
}
for(int i = 1; i <= n; i++)
{
if(num[i] == 0)
num[i] = mx --;
cout << num[i] << " ";
}
}
Compilation message
permutation.cpp:171:2: warning: "/*" within comment [-Wcomment]
171 | /*string A = "15", B = "31";
|
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2796 KB |
Output isn't correct |
