//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 operator-(string a, string b)
{
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
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 < b.size(); i++)
{
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;
}
while(a[a.size() - 1] == '0')
a.pop_back();
reverse(a.begin(), a.end());
return a;
}
string operator+(string a, string b)
{
if(a.size() < b.size())
swap(a, b);
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
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 < b.size(); i++)
{
int x = a[i] - '0' + b[i] - '0' + now;
a[i] = x % 10 + '0';
now = x / 10;
}
while(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());
int now = 1;
for(int i = 0; i < 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[a.size() - 1] == '0')
a.pop_back();
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);
/*string A = "3", B = "1";
cout << A - B << '\n';
//cout << is2(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';
for(int i = 2; i <= n; i++)
{
if(use[i])
continue;
int p = getpar(i - 1);
//cout << i << " " << getpar(i - 1) << '\n';
if(!p)
continue;
if(is2(a[p], a[i]))
ptr = i;
/*else
cout << a[p] << " " << a[i] << '\n';*/
}
//cout << ptr << '\n';
//cout << ptr << '\n';
if(ptr == -1)
break;
num[ptr] = mx --;
par[ptr] = ptr - 1;
use[ptr] = 1;
a[ptr] = a[ptr] - a[getpar(ptr - 1)];
//cout << a[ptr] << '\n';
//cout << '\n';
for(int i = ptr + 1; i <= n; i++)
{
if(!use[i])
a[i] = a[i] - a[ptr];
//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: In function 'std::string operator-(std::string, std::string)':
permutation.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i = 0; i < b.size(); i++)
| ~~^~~~~~~~~~
permutation.cpp: In function 'std::string operator+(std::string, std::string)':
permutation.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < b.size(); i++)
| ~~^~~~~~~~~~
permutation.cpp: In function 'bool is2(std::string, std::string&)':
permutation.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
