Submission #286497

#TimeUsernameProblemLanguageResultExecution timeMemory
286497Dremix10Gondola (IOI14_gondola)C++17
55 / 100
56 ms4728 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll,ll> pl; #define F first #define S second #define endl '\n' #define all(x) (x).begin(),(x).end() #ifdef dremix #define p(x) cerr<<#x<<" = "<<x<<endl; #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl; #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl; #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl; #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl; #else #define p(x) #define p2(x,y) #define pp(x) #define pv(x) #define ppv(x) #endif #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); const int maxp = 22; const ld EPS = 1e-18; const ll INF = 1e18; const int MOD = 1e9+9; const int N = 3e5+1; ll power(ll x, ll n, ll m){ if(n==0)return 1; ll res = power(x,n/2,m); res = (res*res)%m; if(n%2)res = (res*x)%m; return res; } int valid(int n, int arr[]){ map<int,bool> v; int i; int idx = -1; for(i=0;i<n;i++){ if(v[arr[i]]) return 0; v[arr[i]]=1; if(arr[i]<=n)idx = i; } if(idx==-1)return 1; int curr = arr[idx]; for(i=0;i<n;i++){ if(arr[idx]<=n && arr[idx]!=curr)return 0; curr++; idx++; if(curr>n)curr-=n; idx%=n; } return 1; } int replacement(int n, int arr[], int ans[]){ int pos = 0,curr = n+1,idx,maxi = 0; int i; int one = -1; vector<pi> seq; for(i=0;i<n;i++){ if(arr[i]<=n)one = i; else seq.push_back({arr[i],i}); if(arr[i]>maxi){ maxi = arr[i]; idx = i; } } sort(all(seq)); int prev[n]; int val; if(one==-1){ one = 0; val = 1; } else val = arr[one]; for(i=0;i<n;i++){ prev[one] = val; val++; one++; if(val>n)val-=n; one%=n; } for(auto x : seq){ while(curr!=x.F){ ans[pos] = prev[idx]; prev[idx] = curr; curr++; pos++; } ans[pos] = prev[x.S]; prev[x.S] = curr; pos++; curr++; } return pos; } int countReplacement(int n, int arr[]){ if(!valid(n,arr))return 0; ll ans = 1; vector<int> big; ll i; for(i=0;i<n;i++) if(arr[i]>n)big.push_back(arr[i]); sort(all(big)); reverse(all(big)); //int pos = 0; int curr = n+1; if((int)big.size()==n){ ans = n; } for(auto x : big){ ll diff = x-curr; ans = (ans*power(big.size(),diff,MOD))%MOD; curr = x+1; } return ans; }

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:64:28: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     int pos = 0,curr = n+1,idx,maxi = 0;
      |                            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...