This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Oncescu Costin
Nsqrt(NlogN) fara hashuri
doua modulo-uri
CITIRE DESTEAPTA
*/
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int sz[5], N, lg, K, nr, ans[100009], buc[100009], Left[5009], Right[5009];
char sir[50009];
int mod1 = 1e9 + 7, mod2 = 1e9 + 9;
pair < int, int > dp[100009], X[100009], totalDec[10009], unu;
pair < pair < int, int >, int > srt[100009], h[5][10009];
void add (pair < int, int > &x, pair < int, int > y)
{
x.x += y.x; if (x.x >= mod1) x.x -= mod1;
x.y += y.y; if (x.y >= mod2) x.y -= mod2;
}
void substract (pair < int, int > &x, pair < int, int > y)
{
x.x -= y.x; if (x.x < 0) x.x += mod1;
x.y -= y.y; if (x.y < 0) x.y += mod2;
}
void Build (int i)
{
for (int j=Left[i]; j<=Right[i]; j++)
srt[j] = make_pair (X[j], j);
sort (srt + Left[i], srt + Right[i] + 1);
}
void addAndRefresh (int P, int st, pair < int, int > val)
{
memset (sz, 0, sizeof (sz));
for (int i=Left[P]; i<=Right[P]; i++)
if (srt[i].y < st || srt[i].x.x == -1) h[0][++sz[0]] = srt[i];
else
{
bool b1 = 0, b2 = 0;
srt[i].x.x -= val.x;
if (srt[i].x.x < 0) srt[i].x.x += mod1, b1 = 1;
srt[i].x.y -= val.y;
if (srt[i].x.y < 0) srt[i].x.y += mod2, b2 = 1;
int ps = 1 + 2 * b1 + b2;
h[ps][++sz[ps]] = srt[i];
}
for (int i=Right[P]; i>=Left[P]; i--)
{
pair < pair < int, int >, int > curr = {{-2, -2}, -1};
int ps = -1;
for (int j=0; j<5; j++)
if (sz[j] > 0 && curr < h[j][sz[j]])
ps = j, curr = h[j][sz[j]];
if (ps == -1)
{
printf ("Something's terribly wrong");
exit (0);
}
srt[i] = curr, sz[ps] --;
}
}
void Del (int pos)
{
int i = buc[pos];
bool fnd = 0;
for (int j=Right[i]; j>Left[i]; j--)
{
if (srt[j].second == pos) fnd = 1;
if (fnd) srt[j] = srt[j - 1];
}
srt[Left[i]] = {{-1, -1}, -1};
}
void substractSegment (int st, pair < int, int > val)
{
addAndRefresh (buc[st], st, val);
for (int j=buc[st] + 1; j<=nr; j++)
add (totalDec[j], val);
}
int FindLastOne ()
{
for (int i=nr; i>=1; i--)
{
int p = Left[i], u = Right[i], mij, ras = -1;
pair < int, int > wanted = totalDec[i]; add (wanted, unu);
while (p <= u)
{
mij = (p + u) >> 1;
if (srt[mij].first <= wanted) ras = mij, p = mij + 1;
else u = mij - 1;
}
if (ras != -1 && srt[ras].first == wanted)
return srt[ras].second;
}
return -1;
}
int p1[16000], p2[16000];
int main ()
{
scanf ("%d", &N), lg = 0, unu = {1, 1};
while ((1 << lg) <= N) lg ++;
while (K * K <= N * lg) K ++;
p1[0] = p2[0] = 1;
for (int i=1; i<15000; i++)
p1[i] = (1LL * p1[i - 1] * 10) % mod1, p2[i] = (1LL * p2[i - 1] * 10) % mod2;
for (int i=1; i<=N; i++)
{
scanf ("%s", sir);
int l = strlen (sir);
long long alpha = 0, beta = 0;
for (int j=0; j<l; j++)
alpha += 1LL * p1[l - j - 1] * (sir[j] - '0'), beta += 1LL * p2[l - j - 1] * (sir[j] - '0');
dp[i].x = alpha % mod1, dp[i].y = beta % mod2;
}
for (int i=N; i>=1; i--)
substract (dp[i], dp[i - 1]), X[i] = dp[i];
for (int i=1; i<=N; i+=K)
{
Left[++nr] = i;
for (int j=i; j<i + K && j<=N; j++)
buc[j] = nr, Right[nr] = j;
Build (nr);
}
for (int val = 1; val <= N; val ++)
{
int pos = FindLastOne ();
if (pos == -1)
{
printf ("Didn't find the one\n");
return 0;
}
ans[pos] = val, Del (pos);
if (pos < N) substractSegment (pos + 1, dp[pos]);
// printf ("%d\n", pos);
}
for (int i=1; i<=N; i++)
printf ("%d ", ans[i]);
printf ("\n");
return 0;
}
Compilation message (stderr)
permutation.cpp: In function 'int main()':
permutation.cpp:111:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N), lg = 0, unu = {1, 1};
~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
permutation.cpp:119:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%s", sir);
~~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |