제출 #306828

#제출 시각아이디문제언어결과실행 시간메모리
306828vipghn2003곤돌라 (IOI14_gondola)C++14
40 / 100
23 ms2948 KiB
#include "gondola.h" #include<bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair using namespace std; const int mod=1e9+7; const int N=1e5+5; int ST[4*N],lazy[4*N]; void dolazy(int id,int l,int r) { if(lazy[id]==0) return ; ST[id]+=lazy[id]; if(l!=r) { lazy[id*2]+=lazy[id]; lazy[id*2+1]+=lazy[id]; } lazy[id]=0; } void update(int id,int l,int r,int u,int v,int val) { dolazy(id,l,r); if(v<l||u>r) return ; if(u<=l&&r<=v) { ST[id]+=val; if(l!=r) { lazy[id*2]+=val; lazy[id*2+1]+=val; } return ; } int mid=(l+r)/2; update(id*2,l,mid,u,v,val); update(id*2+1,mid+1,r,u,v,val); ST[id]=min(ST[id*2],ST[id*2+1]); } int Power(int x,int n) { if(!n) return 1; if(n%2) return 1ll*Power(x,n-1)*x%mod; int tmp=Power(x,n/2); return 1ll*tmp*tmp%mod; } int expect[N*2],initSeq[N]; int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int offs = 0; int dummy = 0; int mx = -1; memset(expect, -1, sizeof(expect)); for(int i = 0; i < n; i++){ if(gondolaSeq[i] <= n) offs = (n+i-gondolaSeq[i]+1) % n; else expect[gondolaSeq[i]] = i; if(gondolaSeq[i] > mx){ mx = gondolaSeq[i]; dummy = i; } } for(int i = 0; i < n; i++){ initSeq[(i+offs) % n] = i+1; } int rpidx = 0; for(int i = n+1; i <= mx; i++){ if(expect[i] == -1){ replacementSeq[rpidx++] = initSeq[dummy]; initSeq[dummy] = i; }else{ replacementSeq[rpidx++] = initSeq[expect[i]]; initSeq[expect[i]] = i; } } return rpidx; } int countReplacement(int n,int inputSeq[]) { memset(ST,0,sizeof ST); vector<int>b(n),cur; for(int i=0;i<n;i++) inputSeq[i]--; int res=0; int val=0; sort(inputSeq,inputSeq+n); for(int j=1;j<n;j++) if(inputSeq[j]==inputSeq[j-1]) return 0; for(int j=0;j<n;j++) if(inputSeq[j]>(n-1)) cur.push_back(inputSeq[j]-n+1); if(cur.empty()) val=1; else { sort(cur.begin(),cur.end()); int sz=cur.size(); val=Power(sz,cur[0]-1); for(int j=1;j<sz;j++) { if(cur[j]==cur[j-1]) { val=0; break; } val=1ll*val*Power(sz-j,cur[j]-cur[j-1]-1)%mod; } } for(int i=0;i<n;i++) update(1,0,n-1,i,i,inputSeq[i]-i); for(int i=0;i<n;i++) { dolazy(1,0,n-1); if(ST[1]>=0) res=(res+val)%mod; update(1,0,n-1,0,n-1,-1); update(1,0,n-1,n-1-i,n-1-i,n); } return res; } int valid(int n,int inputSeq[]) { return countReplacement(n,inputSeq)!=0; } /* int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; cout<<countReplacement(n,a); } */
#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...