제출 #247636

#제출 시각아이디문제언어결과실행 시간메모리
247636Evirir곤돌라 (IOI14_gondola)C++17
75 / 100
57 ms6264 KiB
#include "gondola.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; void amin(ll &a, ll b){ a=min(a,b); } void amax(ll &a, ll b){ a=max(a,b); } void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";} void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 1e9+9; bool DEBUG = 0; const int MAXN = 100005; const int MAXA = 250005; ll add(ll a,ll b) { a+=b; a%=MOD; if(a<0) a+=MOD; return a; } ll mult(ll a, ll b) { if(a>MOD) a%=MOD; if(b>MOD) b%=MOD; ll ans=(a*b)%MOD; if(ans<0) ans+=MOD; return ans; } ll pw(ll a, ll b) { ll r=1; while(b){ if(b&1) r=mult(r,a); a=mult(a,a); b>>=1; } return r; } ll inverse(ll a) { return pw(a,MOD-2); } int valid(int n, int inputSeq[]) { int minid=0; forn(i,0,n){ if(inputSeq[minid]>inputSeq[i]){ minid=i; } } int tmp[n]; forn(i,0,n){ tmp[i]=inputSeq[(minid+i)%n]; } forn(i,0,n) inputSeq[i]=tmp[i]; set<ll> used; int last=-1; for(int i=0;i<n;i++){ if(used.find(inputSeq[i])!=used.end()) return 0; used.insert(inputSeq[i]); if(inputSeq[i]<=n){ if(last!=-1 && inputSeq[i]-inputSeq[last]!=i-last) return 0; last=i; } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { assert(valid(n, gondolaSeq)); int loc[MAXA]; mset(loc,-1); int large=0; for(int i=0;i<n;i++){ loc[gondolaSeq[i]]=i; if(gondolaSeq[i]>gondolaSeq[large]){ large=i; } } int a[n]; int start=0,val=1; for(int i=0;i<n;i++){ if(gondolaSeq[i]<=n){ start=i; val=gondolaSeq[i]; break; } } for(int i=start;;){ a[i]=val++; if(val==n+1) val=1; i=(i+1)%n; if(i==start) break; } int ptr=0; for(int i=n+1;i<=gondolaSeq[large];i++){ if(loc[i] == -1){ //cout<<"Not found\n"; replacementSeq[ptr++]=a[large]; a[large]=i; } else{ //cout<<"Found\n"; replacementSeq[ptr++] = a[loc[i]]; a[loc[i]]=i; } } return ptr; } int countReplacement(int n, int inputSeq[]) { if(!valid(n, inputSeq)) return 0; vi v; for(int i=0;i<n;i++){ v.pb(inputSeq[i]); } sort(v.begin(), v.end(), greater<ll>()); ll cur=0; while(v.size() && v.back()<=n) v.pop_back(); cur=v.size(); v.pb(n); reverse(v.begin(), v.end()); ll ans=1; for(int i=1;i<v.size();i++){ ans=mult(ans, pw(cur, v[i]-v[i-1]-1)); cur--; } return ans; }

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

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:161:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<v.size();i++){
              ~^~~~~~~~~
#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...