oj.uz

Submission #8904

# Submission time Handle Problem Language Result Execution time Memory
8904 2014-09-23T21:52:36 Z pichulia Gondola (IOI14_gondola) C++
100 / 100
 24 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;
      if(a[i]<300009)
        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;
	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
	{
      res=1;
		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 8 ms 5972 KB Output is correct
7 Correct 12 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 16 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 0 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 24 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 12 ms 5972 KB Output is correct
12 Correct 20 ms 5972 KB Output is correct
13 Correct 20 ms 5972 KB Output is correct
14 Correct 16 ms 5972 KB Output is correct
15 Correct 24 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
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
9 Correct 20 ms 5972 KB Output is correct
10 Correct 16 ms 5972 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 0 ms 5972 KB Output is correct

Subtask #10
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 12 ms 5972 KB Output is correct
10 Correct 16 ms 5972 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 0 ms 5972 KB Output is correct
13 Correct 0 ms 5972 KB Output is correct
14 Correct 20 ms 5972 KB Output is correct
15 Correct 20 ms 5972 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 16 ms 5972 KB Output is correct
18 Correct 8 ms 5972 KB Output is correct