oj.uz

Submission #292808

# Submission time Handle Problem Language Result Execution time Memory
292808 2020-09-07T13:40:39 Z AaronNaidu Gondola (IOI14_gondola) C++14
25 / 100
 15 ms 768 KB 
#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 (n + outOfRange != maxAns)
    {
        return 0;
    }
    if (maxAns > n)
    {
        return 1;
    }
    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;
    }
    return 0;
}

int countReplacement(int n, int inputSeq[]) {
    return 0;
}

Compilation message

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

Subtask #1
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 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

Subtask #2
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
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 15 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 13 ms 768 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 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 6 ms 512 KB Output is correct
7 Correct 13 ms 768 KB Output is correct
8 Correct 11 ms 640 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 13 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 6 ms 640 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 15 ms 768 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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

Subtask #5
0 / 10.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 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 Incorrect 1 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.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
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 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 416 KB Output isn't correct
2 Halted 0 ms 0 KB -