oj.uz

Submission #69651

# Submission time Handle Problem Language Result Execution time Memory
69651 2018-08-21T10:37:48 Z MANcity Gondola (IOI14_gondola) C++14
55 / 100
 31 ms 4400 KB 
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "gondola.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int num[250012];
int valid(int n, int inputSeq[])
{
    for0(i,n-1)
        num[inputSeq[i]]++;
    for1(i,250002)
        if(num[i]>=2)
        {
            return 0;
        }
    for0(i,n-1)
    {
        if(inputSeq[i]<=n)
        {
            int N=inputSeq[i];
            fo(j,i+1,n-1)
            {
                N++;
                if(N>n)
                    N-=n;
                if(inputSeq[j]<=n && inputSeq[j]!=N)
                    return 0;
            }
            fo(j,0,i-1)
            {
                N++;
                if(N>n)
                    N-=n;
                if(inputSeq[j]<=n && inputSeq[j]!=N)
                    return 0;
            }
            return 1;
        }
    }
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    vector<pair<int,int> > V;
    int u=0;
    for0(i,n-1)
    {
        if(gondolaSeq[i]<=n)
        {
            u=1;
            int N=gondolaSeq[i];
            fo(j,i+1,n-1)
            {
                N++;
                if(N>n)
                    N-=n;
                V.push_back(mp(gondolaSeq[j],N));
            }
            fo(j,0,i-1)
            {
                N++;
                if(N>n)
                    N-=n;
                V.push_back(mp(gondolaSeq[j],N));
            }
            break;
        }
    }
    if(u==0)
        for0(i,n-1)
            V.push_back(mp(gondolaSeq[i],i+1));
    int q=(n+1);
    int num=-1;
    sort(V.begin(),V.end());
    for0(i,V.size()-1)
    {
        if(V[i].first!=V[i].second)
        {
            int B=V[i].first;
            int A=V[i].second;
            while(A!=B)
            {
                num++;
                replacementSeq[num]=A;
                A=q;
                q++;
            }
        }
    }
    return (num+1);
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
  return -3;
}
/*
4 5
8 12 2 10 11
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 2 ms 596 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 8 ms 876 KB Output is correct
7 Correct 20 ms 1300 KB Output is correct
8 Correct 13 ms 1300 KB Output is correct
9 Correct 5 ms 1300 KB Output is correct
10 Correct 16 ms 1300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1300 KB Output is correct
2 Correct 3 ms 1300 KB Output is correct
3 Correct 3 ms 1300 KB Output is correct
4 Correct 4 ms 1300 KB Output is correct
5 Correct 3 ms 1300 KB Output is correct
6 Correct 8 ms 1300 KB Output is correct
7 Correct 15 ms 1300 KB Output is correct
8 Correct 22 ms 1300 KB Output is correct
9 Correct 6 ms 1300 KB Output is correct
10 Correct 14 ms 1300 KB Output is correct
11 Correct 2 ms 1300 KB Output is correct
12 Correct 2 ms 1300 KB Output is correct
13 Correct 8 ms 1532 KB Output is correct
14 Correct 2 ms 1532 KB Output is correct
15 Correct 15 ms 1532 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1532 KB Output is correct
2 Correct 3 ms 1532 KB Output is correct
3 Correct 3 ms 1532 KB Output is correct
4 Correct 3 ms 1532 KB Output is correct
5 Correct 2 ms 1532 KB Output is correct
6 Correct 2 ms 1532 KB Output is correct
7 Correct 4 ms 1532 KB Output is correct
8 Correct 4 ms 1532 KB Output is correct
9 Correct 4 ms 1532 KB Output is correct
10 Correct 4 ms 1532 KB Output is correct
11 Correct 20 ms 2608 KB Output is correct
12 Correct 22 ms 3240 KB Output is correct
13 Correct 19 ms 3240 KB Output is correct
14 Correct 20 ms 3956 KB Output is correct
15 Correct 31 ms 4400 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4400 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4400 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4400 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4400 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -