oj.uz

Submission #45373

# Submission time Handle Problem Language Result Execution time Memory
45373 2018-04-13T03:41:21 Z model_code Permutation Recovery (info1cup17_permutation) C++17
100 / 100
 2493 ms 3884 KB 
/*
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

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);
     ~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 620 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 704 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 704 KB Output is correct
5 Correct 860 ms 2204 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 704 KB Output is correct
5 Correct 860 ms 2204 KB Output is correct
6 Correct 2048 ms 3556 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 704 KB Output is correct
5 Correct 860 ms 2204 KB Output is correct
6 Correct 2048 ms 3556 KB Output is correct
7 Correct 2102 ms 3684 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 704 KB Output is correct
5 Correct 860 ms 2204 KB Output is correct
6 Correct 2048 ms 3556 KB Output is correct
7 Correct 2102 ms 3684 KB Output is correct
8 Correct 853 ms 3684 KB Output is correct
9 Correct 2380 ms 3884 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 704 KB Output is correct
5 Correct 860 ms 2204 KB Output is correct
6 Correct 2048 ms 3556 KB Output is correct
7 Correct 2102 ms 3684 KB Output is correct
8 Correct 853 ms 3684 KB Output is correct
9 Correct 2380 ms 3884 KB Output is correct
10 Correct 2493 ms 3884 KB Output is correct