oj.uz

Submission #292872

# Submission time Handle Problem Language Result Execution time Memory
292872 2020-09-07T14:28:44 Z AaronNaidu Gondola (IOI14_gondola) C++14
100 / 100
 98 ms 6752 KB 
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;
const ll mod = 1000000009;
int maxAns;
bool done[300000];
bool used[300000];
map<int, int> mapDone;
int replacedBy[300000];

int valid(int n, int inputSeq[]) {
    int minIndex = -1;
    int minAns = 1000000000;
    int maxIndex = -1;
    maxAns = 0;
    int outOfRange = 0;
    for (int i = 0; i < n; i++)
    {
        if (done[inputSeq[i]])
        {
            return 0;
        }
        done[inputSeq[i]] = true;
        if (inputSeq[i] < minAns)
        {
            minIndex = i;
            minAns = inputSeq[i];
        }
        if (inputSeq[i] > maxAns)
        {
            maxIndex = i;
            maxAns = inputSeq[i];
        }
        if (inputSeq[i] > n)
        {
            outOfRange++;
        }
    }
    if (minAns > n)
    {
        return 1;
    }
    if (n + outOfRange > maxAns)
    {
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (inputSeq[i] <= n)
        {
            int diff = i - minIndex;
            if (diff <= 0)
            {
                diff += n;
            }
            int expectedAns = minAns + diff;
            if (expectedAns <= 0)
            {
                expectedAns += n;
            }
            if (expectedAns%n != inputSeq[i]%n)
            {
                return 0;
            }
        }
    }
    
    return 1;
}

int replacement(int n, int inputSeq[], int replacementSeq[]) {
    int minIndex = -1;
    int minAns = 1000000000;
    int maxIndex = -1;
    int maxAns = 0;
    int outOfRange = 0;
    for (int i = 0; i < n; i++)
    {
        if (inputSeq[i] < minAns)
        {
            minIndex = i;
            minAns = inputSeq[i];
        }
        if (inputSeq[i] > maxAns)
        {
            maxIndex = i;
            maxAns = inputSeq[i];
        }
        if (inputSeq[i] > n)
        {
            outOfRange++;
        }
        used[inputSeq[i]] = true;
    }
    if (minAns <= n)
    {
        for (int i = 0; i < n; i++)
        {
            if (inputSeq[i] > n)
            {
                int diff = i - minIndex;
                
                if (diff <= 0)
                {
                    diff += n;
                }
                int expectedAns = minAns + diff;
                if (expectedAns > n)
                {
                    expectedAns -= n;
                }
                if (expectedAns <= 0)
                {
                    expectedAns += n;
                }
                replacedBy[inputSeq[i]] = expectedAns;
            }
        }
        int currPointer = n;
        int newPointer = n;
        int l = 0;
        while (currPointer < maxAns)
        {
            if (replacedBy[newPointer])
            {
                replacementSeq[l] = replacedBy[newPointer];
                l++;
                for (int j = currPointer+1; j < newPointer; j++)
                {
                    replacementSeq[l] = j;
                    l++;
                }
                currPointer = newPointer;
            }
            newPointer++;
        }
        return l;
    }
    vector<pair<int, int> > v;
    for (int i = 0; i < n; i++)
    {
        v.push_back({inputSeq[i], i});
    }
    sort(v.begin(), v.end());
    int pointer1 = n + 1;
    int l = 0;
    for (int i = 0; i < n; i++)
    {
        replacementSeq[l] = v[i].second + 1;
        l++;
        for (int j = pointer1; j < v[i].first; j++)
        {
            replacementSeq[l] = j;
            l++;
        }
        pointer1 = v[i].first + 1;
    }
    
    return l;
}

ll effExp(ll b, ll e) {
    ll toRet = 1;
    ll exp = b;
    for (int i = 0; i < 32; i++)
    {
        if (e & 1<<i)
        {
            toRet *= exp;
            toRet %= mod;
        }
        exp *= exp;
        exp %= mod;
    }
    return toRet;
}

int finish(int n, int inputSeq[]) {
    vector<int> v;
    int s = 0;
    for (int i = 0; i < n; i++)
    {
        if (inputSeq[i] > n)
        {
            s++;
            v.push_back(inputSeq[i]);
        }
    }
    v.push_back(n);
    sort(v.rbegin(), v.rend());
    ll finAns = 1;
    while (v.size() > 1)
    {
        int missing = v[v.size()-2] - v[v.size()-1] - 1;
        //cout << "Multiply by " << v.size()-1 << " to the " << missing << "\n";
        finAns *= effExp(v.size()-1, missing);
        finAns %= mod;
        v.pop_back();
    }
    return finAns;
}

int countReplacement(int n, int inputSeq[]) {
    int minIndex = -1;
    int minAns = 1000000000;
    int maxIndex = -1;
    maxAns = 0;
    int outOfRange = 0;
    for (int i = 0; i < n; i++)
    {
        if (mapDone.find(inputSeq[i]) != mapDone.end())
        {
            return 0;
        }
        mapDone.insert({inputSeq[i], 1});
        if (inputSeq[i] < minAns)
        {
            minIndex = i;
            minAns = inputSeq[i];
        }
        if (inputSeq[i] > maxAns)
        {
            maxIndex = i;
            maxAns = inputSeq[i];
        }
        if (inputSeq[i] > n)
        {
            outOfRange++;
        }
    }
    if (minAns > n)
    {
        ll nearAns = finish(n, inputSeq);
        nearAns *= n;
        nearAns %= mod;
        return nearAns;
    }
    if (n + outOfRange > maxAns)
    {
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (inputSeq[i] <= n)
        {
            int diff = i - minIndex;
            if (diff <= 0)
            {
                diff += n;
            }
            int expectedAns = minAns + diff;
            if (expectedAns <= 0)
            {
                expectedAns += n;
            }
            if (expectedAns%n != inputSeq[i]%n)
            {
                return 0;
            }
        }
    }
    return finish(n, inputSeq);
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:15:9: warning: variable 'maxIndex' set but not used [-Wunused-but-set-variable]
   15 |     int maxIndex = -1;
      |         ^~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:75:9: warning: variable 'maxIndex' set but not used [-Wunused-but-set-variable]
   75 |     int maxIndex = -1;
      |         ^~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:207:9: warning: variable 'maxIndex' set but not used [-Wunused-but-set-variable]
  207 |     int maxIndex = -1;
      |         ^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 16 ms 768 KB Output is correct
8 Correct 12 ms 640 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 14 ms 792 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 18 ms 720 KB Output is correct
8 Correct 12 ms 640 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 16 ms 768 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 7 ms 616 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 17 ms 768 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 12 ms 768 KB Output is correct
12 Correct 15 ms 768 KB Output is correct
13 Correct 15 ms 1536 KB Output is correct
14 Correct 12 ms 768 KB Output is correct
15 Correct 26 ms 2840 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 64 ms 4472 KB Output is correct
10 Correct 50 ms 3836 KB Output is correct
11 Correct 17 ms 1664 KB Output is correct
12 Correct 22 ms 1920 KB Output is correct
13 Correct 6 ms 768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 60 ms 4472 KB Output is correct
10 Correct 48 ms 3960 KB Output is correct
11 Correct 18 ms 1664 KB Output is correct
12 Correct 22 ms 1920 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 80 ms 5240 KB Output is correct
15 Correct 98 ms 6752 KB Output is correct
16 Correct 15 ms 1592 KB Output is correct
17 Correct 59 ms 4600 KB Output is correct
18 Correct 31 ms 2944 KB Output is correct