oj.uz

Submission #8902

# Submission time Handle Problem Language Result Execution time Memory
8902 2014-09-23T21:50:57 Z pichulia Gondola (IOI14_gondola) C++
75 / 100
 28 ms 5972 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
#include"gondola.h"
#define M 1000000009
int n;
int a[100009];
int b[100009];
int x[100009];
int xl;
int y[300009];
int nono;
long long int res = 1;
int resb[300009];
int rl;
bool not_gon()
{
    int i, j;
    for(i=0;i<n;i++)
    {
        x[xl++] = a[i];
        b[i] = i+1;
        y[a[i]]=i;
    }
    for(i=0;i<n;i++)
    {
        if(a[i]<=n)
            break;
    }
    sort(x,x+xl);
    xl = unique(x,x+xl)-x;
    if(xl<n) return true;
    if(i==n) return xl<n;
    nono = 1;
    for(j=0;j<n;j++)
    {
        int k = (i+j)%n;
        b[k] = (a[i] + j-1)%n+1;
        if(a[k] > n || a[k] == (a[i] + j-1)%n+1) continue;
        return true;
    }
    return false;
}
long long int poww(long long p, long long q)
{
	long long int x,z;
	x=1;z=p;
	while(q)
	{
		if(q%2){x = (x*z)%M;}
		z= (z*z)%M;
		q/=2;
	}
	return x;
}
void process()
{
	int i, j, k;
	int save = n;
	int last;
	for(i=0;i<xl;i++)
		if(x[i] > n)
			break;
	save = n - i;
	last = n;
	res = 1;
	for(;i<xl;i++)
	{
		res = (res * poww(save,x[i] - last - 1))%M;
		save--;
		last = x[i];
	}
}
void process2()
{
	int i, j, k;
	int save = n;
	int last;
	for(i=0;i<xl;i++)
		if(x[i] > n)
			break;
	rl = 0;
	last = n;
	for(;i<xl;i++)
	{
		resb[rl++] = b[y[x[i]]];
		for(j=last+1;j<x[i];j++)
		{
			resb[rl++] = j;
		}
		last = x[i];
	}
}
int valid(int _n,int inputSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
		a[i] = inputSeq[i];
	if(not_gon())
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

int countReplacement(int _n, int inputSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
	{
		a[i] = inputSeq[i];
	}
  nono = 0;
	if(not_gon())
	{
		return 0;
	}
	else
	{
		if(nono==0)
		res = n;
		process();
		return res;
	}
}
int replacement(int _n, int gondolaSeq[], int replacementSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
		a[i] = gondolaSeq[i];
  if(not_gon())
    return 0;
	process2();
	resb[rl] = 0;
	for(i=0;i<rl;i++)
		replacementSeq[i] = resb[i];
  return rl;

}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5972 KB Output is correct
2 Correct 0 ms 5972 KB Output is correct
3 Correct 0 ms 5972 KB Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5972 KB Output is correct
2 Correct 0 ms 5972 KB Output is correct
3 Correct 0 ms 5972 KB Output is correct
4 Correct 0 ms 5972 KB Output is correct
5 Correct 0 ms 5972 KB Output is correct
6 Correct 0 ms 5972 KB Output is correct
7 Correct 0 ms 5972 KB Output is correct
8 Correct 0 ms 5972 KB Output is correct
9 Correct 12 ms 5972 KB Output is correct
10 Correct 16 ms 5972 KB Output is correct
11 Correct 8 ms 5972 KB Output is correct
12 Correct 8 ms 5972 KB Output is correct
13 Incorrect 0 ms 5972 KB Output isn't correct

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5972 KB Output is correct
2 Correct 0 ms 5972 KB Output is correct
3 Correct 0 ms 5972 KB Output is correct
4 Correct 0 ms 5972 KB Output is correct
5 Correct 0 ms 5972 KB Output is correct
6 Correct 0 ms 5972 KB Output is correct
7 Correct 0 ms 5972 KB Output is correct
8 Correct 0 ms 5972 KB Output is correct
9 Correct 16 ms 5972 KB Output is correct
10 Correct 12 ms 5972 KB Output is correct
11 Correct 8 ms 5972 KB Output is correct
12 Correct 0 ms 5972 KB Output is correct
13 Incorrect 0 ms 5972 KB Output isn't correct
14 Halted 0 ms 0 KB -