Submission #292823

#	Time	Username	Problem	Language	Result	Execution time	Memory
292823		AaronNaidu	Gondola (IOI14_gondola)	C++14	60 / 100	24 ms	2816 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;

bool done[300000];
bool used[300000];
int replacedBy[300000];

int valid(int n, int inputSeq[]) {
    int minIndex = -1;
    int minAns = 1000000000;
    int maxIndex = -1;
    int 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 countReplacement(int n, int inputSeq[]) {
    int minIndex = -1;
    int minAns = 1000000000;
    int maxIndex = -1;
    int 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;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:12:9: warning: variable 'maxIndex' set but not used [-Wunused-but-set-variable]
   12 |     int maxIndex = -1;
      |         ^~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:72:9: warning: variable 'maxIndex' set but not used [-Wunused-but-set-variable]
   72 |     int maxIndex = -1;
      |         ^~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:163:9: warning: variable 'maxIndex' set but not used [-Wunused-but-set-variable]
  163 |     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