제출 #150595

#제출 시각아이디문제언어결과실행 시간메모리
150595서울대학교 연구공원 944동 삼성전자서울대연구소 (#200)포도주 시음 (FXCUP4_wine)C++17
0 / 100
1101 ms1024 KiB
#include "bartender.h" #include<bits/stdc++.h> using namespace std; static __int128 fact[31]; __int128 P2I(std::vector<int> R) { if(R.size() == 0) return 0; __int128 ans = R[0]*fact[R.size()-1]; vector<int> R2; for(int i=1; i<(int)R.size(); ++i) { if(R[i] > R[0]) R2.push_back(R[i]-1); else R2.push_back(R[i]); } return ans + P2I(R2); } vector<int> I2D(int K, int N, __int128 x) { vector<int> V(N); for(int i=N-1; i>=0; --i) { V[i] = x%K; x /= K; } return V; } static void Init(int N) { fact[0] = 1; for(int i=1; i<=N; ++i) fact[i] = i*fact[i-1]; } std::vector<int> BlendWines(int K, std::vector<int> R){ Init(R.size()); for(auto&x:R) --x; vector<int> A = I2D(K, R.size(), P2I(R)); for(auto&x:A)++x; return A; }
#include "taster.h" #include<bits/stdc++.h> using namespace std; static __int128 fact[31]; vector<int> I2P(int N, __int128 v) { if(N == 0) { vector<int> R2; return R2; } vector<int> R2 = I2P(N-1, v%fact[N-1]); vector<int> R; R.push_back(v/fact[N-1]); for(int i=0; i<N-1; ++i) { if(R2[i] >= R[0]) R.push_back(R2[i]+1); else R.push_back(R2[i]); } return R; } __int128 D2I(int K, vector<int> V) { __int128 ans = 0; for(int i=0; i<(int)V.size(); ++i) ans = ans*K+V[i]; return ans; } static void Init(int N) { fact[0] = 1; for(int i=1; i<=N; ++i) fact[i] = i*fact[i-1]; } __int128 p(int a, int b) { __int128 x = 1; for(int i=0; i<b; ++i) x *= a; return x; } vector<tuple<int, int, int> > TR; bool test(vector<int> R) { for(auto x: TR) { auto [a,b,c] = x; if( (R[a]<R[b]) != (c==-1)) return false; } return true; } std::vector<int> SortWines(int K, std::vector<int> A) { Init(A.size()); for(auto&x:A) --x; __int128 aa = D2I(K, A); vector<pair<int, int> > tt; for(int i=0; i<(int)A.size(); ++i) for(int j=0; j<i; ++j) if(A[i]+A[j] <= K-2) { //printf("%d %d\n", A[i], A[j]); tt.emplace_back(i, j); } mt19937_64 rng(573); shuffle(tt.begin(), tt.end(), rng); for(int i=0; i<min((int)tt.size(),30); ++i) { //printf("%d %d\n",A[tt[i].first], A[tt[i].second]); TR.emplace_back(tt[i].first, tt[i].second, Compare(tt[i].first, tt[i].second)); } while(true) { vector<int> R = I2P(A.size(), aa); for(auto&x:R)++x; if(test(R)) return R; aa += p(K, A.size()); } }
#Verdict Execution timeMemoryGrader output
Fetching results...