Submission #308495

#	Time	Username	Problem	Language	Result	Execution time	Memory
308495		amunduzbaev	Gondola (IOI14_gondola)	C++14	60 / 100	32 ms	3092 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
const int N=(300000);
#define ll long long
int used[N];
int vis[1000001], res1[1000001];
pair <int, int> arr[1000001];
ll x[1000001], mod = 1e9+9;
map <int, int> vis1;
ll binpow (ll a, ll b) {
	if (b == 0)
		return 1ll;
	if (b % 2 == 1)
		return binpow (a, b-1) * 1ll *  a % mod;
	else {
		int c = binpow (a, b/2);
		return c * 1ll *  c % mod;
	}
}
int valid(int n, int a[]){
    bool b=0;
    int i;

    for(i=0;i<n;i++){
        if(used[a[i]])
            return 0;
        used[a[i]]++;
    }

    for(i=0;i<n;i++){
        if(a[i] <= n){
            b=1;
            break;
        }
    }
    if(!b) return 1;
    int t=a[i];
    for(int j=0;j<n;j++){
        if(a[i]<=n){
            if(a[i]!=t) return 0;
        }
        t++;
        i++;
        if(t>n) t=1;
        if(i==n) i=0;
    }
    return 1;
}

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

int replacement(int n, int a[], int ans[])
{
    int m = 0,mi = 0, ind = 0, num = 0,cnt = 0;
    for(int i = 0 ; i < n; i++){
        arr[i] = make_pair(a[i] , i+1);
        vis[a[i]]=1;
        if( a[i]>=1 && a[i] <=n ){
            ind = i+1;
            num = a[i];
        }
        if ( m <  a[i]){
            m =  a[i];
            mi =i;
        }
    }
    sort(arr, arr + n);
    vector <int > v;

    if(num == 0){
        for(int i = m-1; i>n;i--){
            if(vis[i]==0)
                v.push_back(i);
        }

        for(int i= 0; i < n ;i++){
            int t = arr[i].second;
            int p = arr[i].first;
            ans[cnt]=t;
            cnt ++;
                while( v.size () >  0 && p > v.back()){
                    ans[cnt]=v.back();
                    cnt ++;
                    v.pop_back();
                }
            }
        return m-n;
    }
    for(int i =1; i <=n ;i++){
        res1[i-1] = (num + i -ind + n)%n ;
        if(res1[i-1]==0)
            res1[i-1]=n;
    }
    for(int i = m-1; i>n;i--){
        if(vis[i]==0)
            v.push_back(i);
    }
    for(int i =0 ; i <n;i++){
        int t = arr[i].second;
        int p = arr[i].first;
        if(a[t-1]!=res1[t-1]){
            ans[cnt]=res1[t-1];
            cnt ++;
            while( v.size () >  0 && a[t-1] > v.back()){
                ans[cnt]=v.back();
                cnt ++;
                v.pop_back();
            }
        }
    }

  return m - n;
}

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

int countReplacement(int n, int a[])
{
    int ind = 0,num = 0;
    for(int i = 0 ; i< n ; i++){
        if(a[i]>=1 && a[i] <=n ){
            ind = i;
            num = a[i];
        }
    if(a[i] <1)         return 0;
    if(vis1[a[i]] ==1)  return 0;
    
    vis1[a[i]]=1;
    
    }
    if(num!=0)
    for(int i = 0 ; i < n; i++)
        if(a[i] <= n){
            if( (ind  +  (a[i] - num)  +n ) %n!=i  )
            return 0;
        }
    sort(a, a + n);
    for(int i = 0 ; i < n; i++)
        x[i] = a[i];
    bool t=true;
    ll ans=  1ll;
    for(int i = 0; i < n ; i++ ){
        if(x[i] > n){
            if(t){
                ans *= 1ll * binpow( (n- i), (x[i] - n - 1) ) % mod;
            }
            else{
                ans *= 1ll * binpow( (n- i), x[i] - x[i-1] - 1) % mod;
            }
            t=false;
        }
    }
        if(x[0] > n)
        ans = ans * 1ll * n % mod;
        return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:102:13: warning: unused variable 'p' [-Wunused-variable]
  102 |         int p = arr[i].first;
      |             ^
gondola.cpp:56:15: warning: variable 'mi' set but not used [-Wunused-but-set-variable]
   56 |     int m = 0,mi = 0, ind = 0, num = 0,cnt = 0;
      |               ^~

• 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