제출 #306848

#제출 시각아이디문제언어결과실행 시간메모리
306848vipghn2003곤돌라 (IOI14_gondola)C++14
60 / 100
24 ms3320 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]; 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]--; b[i]=inputSeq[i]; } int res=0; int val=0; sort(b.begin(),b.end()); for(int j=1;j<n;j++) if(b[j]==b[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; } } if(cur.size()==n) res=1ll*val*n%mod; else { int id; for(int j=0;j<n;j++) { if(inputSeq[j]<=(n-1)) id=j; } int cnt=inputSeq[id]; for(int j=id,k=1;k<=n;j=(j+1)%n,k++) { if(inputSeq[j]<n&&inputSeq[j]!=cnt) return 0; cnt=(cnt+1)%n; } res=val; } 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); }*/

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:85:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |     if(cur.size()==n) res=1ll*val*n%mod;
      |        ~~~~~~~~~~^~~
gondola.cpp:93:26: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         int cnt=inputSeq[id];
      |                          ^~
#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...