Submission #292869

#	Time	Username	Problem	Language	Result	Execution time	Memory
292869		AaronNaidu	Gondola (IOI14_gondola)	C++14	60 / 100	31 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];
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);
        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 (stderr)

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:206:9: warning: variable 'maxIndex' set but not used [-Wunused-but-set-variable]
  206 |     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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10