#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left ind+ind
#define right ind+ind+1
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'
const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 705;
const int M = 60;
const int SQ = 350;
const int MOD = 998244353;
typedef long long ll;
typedef pair<ll,ll> lll;
typedef pair<ll,int> lli;
typedef pair<int,int> ii;
#define EL printf("\n")
#define OK printf("OK")
#define pb push_back
#define mp make_pair
#define ep emplace_back
#define X first
#define Y second
#define fillchar(a,x) memset(a, x, sizeof(a))
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)
const int base = 1e9;
typedef vector<int> BigInt;
void Set(BigInt &a) {
while (a.size() > 1 && a.back() == 0) a.pop_back();
}
void Print(BigInt a) {
Set(a);
printf("%d", (a.size() == 0) ? 0 : a.back());
FORD(i,a.size()-2,0) printf("%09d", a[i]); EL;
}
BigInt Integer(string s) {
BigInt ans;
if (s[0] == '-') return ans;
if (s.size() == 0) {ans.pb(0); return ans;}
while (s.size()%9 != 0) s = '0'+s;
for (int i=0;i<s.size();i+=9) {
int v = 0;
for (int j=i;j<i+9;j++) v = v*10+(s[j]-'0');
ans.insert(ans.begin(),v);
}
Set(ans);
return ans;
}
BigInt Integer(char c[]) {
string s = "";
FOR(i,0,strlen(c)-1) s = s + c[i];
return Integer(s);
}
BigInt Integer(ll x) {
string s = "";
while (x > 0) s = char(x%10+'0') + s, x /= 10;
return Integer(s);
}
BigInt Integer(int x) {
return Integer((ll) x);
}
void operator >> (istream &in, BigInt &a) {
string s;
getline(cin, s);
a = Integer(s);
}
void operator << (ostream &out, BigInt a) {
Print(a);
}
bool operator < (BigInt a, BigInt b) {
Set(a);
Set(b);
if (a.size() != b.size()) return (a.size() < b.size());
FORD(i,a.size()-1,0)
if (a[i] != b[i]) return (a[i] < b[i]);
return false;
}
bool operator > (BigInt a, BigInt b) {
return (b < a);
}
bool operator == (BigInt a, BigInt b) {
return (!(a < b) && !(b < a));
}
bool operator <= (BigInt a, BigInt b) {
return (a < b || a == b);
}
bool operator >= (BigInt a, BigInt b) {
return (b < a || b == a);
}
bool operator < (BigInt a, int b) {
return (a < Integer(b));
}
bool operator > (BigInt a, int b) {
return (a > Integer(b));
}
bool operator == (BigInt a, int b) {
return (a == Integer(b));
}
bool operator >= (BigInt a, int b) {
return (a >= Integer(b));
}
bool operator <= (BigInt a, int b) {
return (a <= Integer(b));
}
BigInt max(BigInt a, BigInt b) {
if (a > b) return a;
return b;
}
BigInt min(BigInt a, BigInt b) {
if (a < b) return a;
return b;
}
BigInt operator + (BigInt a, BigInt b) {
Set(a);
Set(b);
BigInt ans;
int carry = 0;
FOR(i,0,max(a.size(), b.size())-1) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
ans.pb(carry%base);
carry /= base;
}
if (carry) ans.pb(carry);
Set(ans);
return ans;
}
BigInt operator + (BigInt a, int b) {
return a + Integer(b);
}
BigInt operator ++ (BigInt &a) { // ++a
a = a + 1;
return a;
}
void operator += (BigInt &a, BigInt b) {
a = a + b;
}
void operator += (BigInt &a, int b) {
a = a + b;
}
BigInt operator - (BigInt a, BigInt b) {
Set(a);
Set(b);
BigInt ans;
int carry = 0;
FOR(i,0,a.size()-1) {
carry += a[i] - (i < b.size() ? b[i] : 0);
if (carry < 0) ans.pb(carry+base), carry = -1;
else ans.pb(carry), carry = 0;
}
Set(ans);
return ans;
}
BigInt operator - (BigInt a, int b) {
return a - Integer(b);
}
void operator -- (BigInt &a) { // --a
a = a - 1;
}
void operator -= (BigInt &a, BigInt b) {
a = a + b;
}
void operator -= (BigInt &a, int b) {
a = a - b;
}
BigInt operator * (BigInt a, BigInt b) {
Set(a);
Set(b);
BigInt ans;
ans.assign(a.size()+b.size(), 0);
FOR(i,0,a.size()-1) {
ll carry = 0ll;
for (int j=0;j<b.size() || carry > 0;j++) {
ll s = ans[i+j] + carry + (ll)a[i]*(j<b.size()?(ll)b[j]:0ll);
ans[i+j] = s%base;
carry = s/base;
}
}
Set(ans);
return ans;
}
BigInt operator * (BigInt a, int b) {
return a * Integer(b);
}
void operator *= (BigInt &a, BigInt b) {
a = a * b;
}
void operator *= (BigInt &a, int b) {
a = a * b;
}
BigInt operator / (BigInt a, BigInt b) {
Set(a);
Set(b);
if (b == Integer(0)) return Integer("-1");
BigInt ans, cur;
FORD(i,a.size()-1,0) {
cur.insert(cur.begin(), a[i]);
int x = 0, L = 0, R = base;
while (L <= R) {
int mid = (L+R)>>1;
if (b*Integer(mid) > cur) {
x = mid;
R = mid-1;
}
else
L = mid+1;
}
cur = cur - Integer(x-1)*b;
ans.insert(ans.begin(),x-1);
}
Set(ans);
return ans;
}
BigInt operator / (BigInt a, int b) {
Set(a);
BigInt ans;
ll cur = 0ll;
FORD(i,a.size()-1,0) {
cur = (cur*(ll)base + (ll)a[i]);
ans.insert(ans.begin(),cur/b);
cur %= b;
}
Set(ans);
return ans;
}
void operator /= (BigInt &a, BigInt b) {
a = a / b;
}
void operator /= (BigInt &a, int b) {
a = a / b;
}
BigInt operator % (BigInt a, BigInt b) {
Set(a);
Set(b);
if (b == Integer(0)) return Integer("-1");
BigInt ans;
FORD(i,a.size()-1,0) {
ans.insert(ans.begin(), a[i]);
int x = 0, L = 0, R = base;
while (L <= R) {
int mid = (L+R)>>1;
if (b*Integer(mid) > ans) {
x = mid;
R = mid-1;
}
else
L = mid+1;
}
ans = ans - Integer(x-1)*b;
}
Set(ans);
return ans;
}
int operator % (BigInt a, int b) {
Set(a);
if (b == 0) return -1;
int ans = 0;
FORD(i,a.size()-1,0)
ans = (ans*(base%b) + a[i]%b)%b;
return ans;
}
void operator %= (BigInt &a, BigInt b) {
a = a % b;
}
void operator %= (BigInt &a, int b) {
a = a % Integer(b);
}
BigInt gcd(BigInt a, BigInt b) {
Set(a);
Set(b);
while (b > Integer(0)) {
BigInt r = a%b;
a = b;
b = r;
}
Set(a);
return a;
}
BigInt lcm(BigInt a, BigInt b) {
return (a*b/gcd(a,b));
}
BigInt sqrt(BigInt a) {
BigInt x0 = a, x1 = (a+1)/2;
while (x1 < x0) {
x0 = x1;
x1 = (x1+a/x1)/2;
}
return x0;
}
BigInt pow(BigInt a, BigInt b) {
if (b == Integer(0)) return Integer(1);
BigInt tmp = pow(a, b/2);
if (b%2 == 0) return tmp * tmp;
return tmp * tmp * a;
}
BigInt pow(BigInt a, int b) {
return pow(a,(Integer(b)));
}
int log(int n, BigInt a) { // log_n(a)
Set(a);
int ans = 0;
while (a > Integer(1)) {
ans++;
a /= n;
}
return ans;
}
int n,a[N],mark[N];
BigInt q[N],is[N];
string s;
int main() {
scanf("%d",&n);
assert(n <= 700);
for (int i = 1 ; i <= n ; i++) {
cin >> s;
q[i] = Integer(s);
}
a[1] = 1;
is[1] = Integer("1");
for (int i = 2 ; i <= n ; i++) {
int say = 0;
BigInt diff = Integer("0");
BigInt cnt = Integer("0");
diff += q[i] - q[i - 1] - 1;
// Print(diff);
vector <ii> v;
memset(mark,0,sizeof mark);
for (int j = 1 ; j < i ; j++)
v.pb(mp(a[j],j));
sort(v.begin(),v.end());
for (int j = 0 ; j < len(v) ;j++) {
// Print(diff);
if (diff == 0) break;
int x = v[j].sc;
// Print(is[a[x]]);
// Print(diff);
diff = diff - is[a[x]];
// Print(diff);
say++;
cnt += is[a[x]];
mark[x] = 1;
}
for (int j = len(v) - 1; j >= 0 ; j--) {
int x = v[j].sc;
if (mark[x] == 0) {
is[a[x] + 1] = is[a[x]];
a[x]++;
}
}
a[i] = say + 1;
is[a[i]] = Integer("0");
is[a[i]] += cnt + 1;
// printf("\n\n\n");
}
for (int i = 1 ; i <= n ; i++) {
cout << a[i] << " ";
}
}
Compilation message
permutation.cpp: In function 'BigInt Integer(std::__cxx11::string)':
permutation.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<s.size();i+=9) {
~^~~~~~~~~
permutation.cpp: In function 'BigInt Integer(char*)':
permutation.cpp:39:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for (int i=l;i<=r;i++)
permutation.cpp:73:9:
FOR(i,0,strlen(c)-1) s = s + c[i];
~~~~~~~~~~~~~~~
permutation.cpp:73:5: note: in expansion of macro 'FOR'
FOR(i,0,strlen(c)-1) s = s + c[i];
^~~
permutation.cpp: In function 'BigInt operator+(BigInt, BigInt)':
permutation.cpp:39:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for (int i=l;i<=r;i++)
permutation.cpp:168:9:
FOR(i,0,max(a.size(), b.size())-1) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
permutation.cpp:168:5: note: in expansion of macro 'FOR'
FOR(i,0,max(a.size(), b.size())-1) {
^~~
permutation.cpp:169:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < a.size()) carry += a[i];
~~^~~~~~~~~~
permutation.cpp:170:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < b.size()) carry += b[i];
~~^~~~~~~~~~
permutation.cpp: In function 'BigInt operator-(BigInt, BigInt)':
permutation.cpp:39:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for (int i=l;i<=r;i++)
permutation.cpp:204:9:
FOR(i,0,a.size()-1) {
~~~~~~~~~~~~~~
permutation.cpp:204:5: note: in expansion of macro 'FOR'
FOR(i,0,a.size()-1) {
^~~
permutation.cpp:205:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
carry += a[i] - (i < b.size() ? b[i] : 0);
~~^~~~~~~~~~
permutation.cpp: In function 'BigInt operator*(BigInt, BigInt)':
permutation.cpp:39:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for (int i=l;i<=r;i++)
permutation.cpp:237:9:
FOR(i,0,a.size()-1) {
~~~~~~~~~~~~~~
permutation.cpp:237:5: note: in expansion of macro 'FOR'
FOR(i,0,a.size()-1) {
^~~
permutation.cpp:239:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0;j<b.size() || carry > 0;j++) {
~^~~~~~~~~
permutation.cpp:240:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ll s = ans[i+j] + carry + (ll)a[i]*(j<b.size()?(ll)b[j]:0ll);
~^~~~~~~~~
permutation.cpp: In function 'BigInt operator/(BigInt, BigInt)':
permutation.cpp:266:45: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
if (b == Integer(0)) return Integer("-1");
^
permutation.cpp: In function 'BigInt operator%(BigInt, BigInt)':
permutation.cpp:313:45: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
if (b == Integer(0)) return Integer("-1");
^
permutation.cpp: In function 'int main()':
permutation.cpp:417:21: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
is[1] = Integer("1");
^
permutation.cpp:420:28: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
BigInt diff = Integer("0");
^
permutation.cpp:421:27: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
BigInt cnt = Integer("0");
^
permutation.cpp:449:25: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
is[a[i]] = Integer("0");
^
permutation.cpp:407:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
45 ms |
484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
45 ms |
484 KB |
Output is correct |
| 3 |
Correct |
296 ms |
696 KB |
Output is correct |
| 4 |
Correct |
374 ms |
816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
45 ms |
484 KB |
Output is correct |
| 3 |
Correct |
296 ms |
696 KB |
Output is correct |
| 4 |
Correct |
374 ms |
816 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
45 ms |
484 KB |
Output is correct |
| 3 |
Correct |
296 ms |
696 KB |
Output is correct |
| 4 |
Correct |
374 ms |
816 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
45 ms |
484 KB |
Output is correct |
| 3 |
Correct |
296 ms |
696 KB |
Output is correct |
| 4 |
Correct |
374 ms |
816 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
45 ms |
484 KB |
Output is correct |
| 3 |
Correct |
296 ms |
696 KB |
Output is correct |
| 4 |
Correct |
374 ms |
816 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
45 ms |
484 KB |
Output is correct |
| 3 |
Correct |
296 ms |
696 KB |
Output is correct |
| 4 |
Correct |
374 ms |
816 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
