제출 #705678

#제출 시각아이디문제언어결과실행 시간메모리
705678ToroTN곤돌라 (IOI14_gondola)C++14
60 / 100
32 ms5316 KiB
#include<bits/stdc++.h> using namespace std; #include "gondola.h" //#include "grader.cpp" #define X first #define Y second #define pb push_back #define ll long long int a[100005]; int valid(int n, int inputSeq[]) { set<int> s; int type=1,pos[100005]; for(int i=0;i<n;i++) { a[i+1]=inputSeq[i]; } for(int i=1;i<=n;i++) { if(a[i]<=n)pos[a[i]]=i; s.insert(a[i]); } if(s.size()<n)type=0; for(int i=1;i<n;i++) { if((!(pos[i]==n&&pos[i+1]==1)&&!(pos[i]+1==pos[i+1]))&&(pos[i]>=1&&pos[i]<=n)&&(pos[i+1]>=1&&pos[i+1]<=n)) { type=0; } } if((!(pos[n]==n&&pos[1]==1)&&!(pos[n]+1==pos[1]))&&(pos[n]>=1&&pos[1]<=n)&&(pos[n]>=1&&pos[1]<=n))type=0; return type; } //---------------------- int replacement(int n, int gondolaSeq[], int peteza[]) { for(int i=0;i<n;i++) { a[i+1]=gondolaSeq[i]; } int mx=0,origin[100005]; for(int i=1;i<=n;i++)mx=max(mx,a[i]),origin[i]=i; for(int i=1;i<=n;i++) { if(a[i]<=n) { for(int j=i;j<i+n;j++) { if(j<=n) { if(a[i]+j-i<=n) { origin[j]=a[i]+j-i; }else { origin[j]=a[i]+j-i-n; } }else { if(a[i]+j-i<=n) { origin[j-n]=a[i]+j-i; }else { origin[j-n]=a[i]+j-i-n; } } } break; } } int it=-1; vector<pair<int,int> > v; v.pb({-1e9,-1e9}); for(int i=1;i<=n;i++)v.pb({a[i],origin[i]}); sort(v.begin(),v.end()); for(int i=1;i<=n;i++) { if(v[i].X>n) { ++it; peteza[it]=v[i].Y; if(v[i-1].X>n) { for(int j=v[i-1].X+1;j<v[i].X;j++) { ++it; peteza[it]=j; } }else { for(int j=n+1;j<v[i].X;j++) { ++it; peteza[it]=j; } } } } return mx-n; } //---------------------- ll MOD=1e9+9; ll power(ll base,ll num) { ll powerx[35]; powerx[0]=base; for(int i=1;i<=30;i++) { powerx[i]=powerx[i-1]*powerx[i-1]; powerx[i]%=MOD; } vector<ll> vec; while(1) { if(num<=1) { vec.pb(num); break; } vec.pb(num%2); num/=2; } ll super=1; for(int i=0;i<vec.size();i++) { if(vec[i]==1) { super*=powerx[i]; super%=MOD; } } return super; } int countReplacement(int n, int inputSeq[]) { int num=valid(n,inputSeq); if(num==0)return 0; /*for(int i=0;i<n;i++) { a[i+1]=inputSeq[i]; } ll ans=1,cnt=0; vector<ll> v; v.pb(-1e9); for(int i=1;i<=n;i++) { if(a[i]>n) { v.pb(a[i]); ++cnt; } } sort(v.begin(),v.end()); if(v.size()>=2) { for(int i=1;i<v.size();i++) { ll kuay; if(i==1) { kuay=v[i]-n-1; }else { kuay=v[i]-v[i-1]-1; } //printf("%lld %lld\n",cnt,kuay); ans*=power(cnt,kuay); ans%=MOD; --cnt; } //printf("\n"); } if(v.size()==n+1) { ans*=n; ans%=MOD; } return ans;*/ ll ans=1; vector<int> v; int cnt=n; for (int i=0; i<n; ++i) { if (inputSeq[i]<=n) --cnt; else v.push_back(inputSeq[i]); } if (cnt==n) ans=n; v.push_back(n); sort(v.begin(),v.end()); for (int i=1; i<v.size(); ++i) { ll h=(ans*power(cnt,v[i]-v[i-1]-1))%MOD; ans=h; --cnt; } return ans; }

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

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:23:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     if(s.size()<n)type=0;
      |        ~~~~~~~~^~
gondola.cpp: In function 'long long int power(long long int, long long int)':
gondola.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:197:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for (int i=1; i<v.size(); ++i) {
      |                   ~^~~~~~~~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:31:27: warning: 'pos[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |     if((!(pos[n]==n&&pos[1]==1)&&!(pos[n]+1==pos[1]))&&(pos[n]>=1&&pos[1]<=n)&&(pos[n]>=1&&pos[1]<=n))type=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...