Submission #292851

#	Time	Username	Problem	Language	Result	Execution time	Memory
292851		AaronNaidu	Gondola (IOI14_gondola)	C++14	75 / 100	23 ms	2808 KiB

gondola

#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];
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;
}

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]);
        }
    }
    sort(v.rbegin(), v.rend());
    int pointer1 = n + 1;
    ll finAns = 1;
    while (v.size())
    {
        //cout << "pointer is " << pointer1 << "\n";
        if (v[v.size()-1] == pointer1)
        {
            v.pop_back();
            pointer1++;
        }
        else
        {
            finAns *= v.size();
            finAns %= mod;
            pointer1++;
        }
    }
    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 (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 finish(n, inputSeq);
    }
    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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10