제출 #967015

#제출 시각아이디문제언어결과실행 시간메모리
967015RequiemVrtić (COCI18_vrtic)C++17
32 / 160
2 ms2652 KiB
#include<bits/stdc++.h> //#define int long long #define pb push_back #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #define MOD 1000000007 #define INF 1e18 #define fi first #define se second #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>=b;i--) #define sz(a) ((int)(a).size()) #define endl '\n' #define pi 3.14159265359 #define TASKNAME "vrtic" template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; const int MAXN = 159; int n; int best_friend[MAXN], bag_of_candy[MAXN]; namespace subtask1{ bool checkSubtask1(){ for(int i = 1; i <= n; i++){ if (best_friend[i] != i % n + 1) return false; } return true; } int arr[MAXN]; void solveSubtask1(){ int res = 0, splitting_point = 0; sort(bag_of_candy + 1, bag_of_candy + 1 + n); int cur = 0; for(int i = 3; i <= n; i++){ maximize(res, abs(bag_of_candy[i] - bag_of_candy[i - 2])); } cout << res << endl; for(int i = 1; i <= n; i += 2){ cout << bag_of_candy[i] << ' '; } for(int i = n - (n & 1); i > 0; i -= 2){ cout << bag_of_candy[i] << ' '; } cout << endl; } } namespace subtask2{ //not usable yet bool checkSubtask2(){ return n <= 20; } int MinDistriRange[MAXN][MAXN], ok[MAXN], answer[MAXN]; vector<vector<int>> Listcycle; vector<ii> Nxtmask; int dp[21][(1 << 20)], trace[21][(1 << 20)]; void prep(){ sort(bag_of_candy + 1, bag_of_candy + 1 + n); for(int i = 1; i <= n; i++){ for(int j = i; j <= n; j++){ int length = j - i + 1; if (length == 1) MinDistriRange[i][j] = 0; else if (length == 2) MinDistriRange[i][j] = abs(bag_of_candy[j] - bag_of_candy[i]); else { for(int k = i + 2; k <= j; k++){ maximize(MinDistriRange[i][j], abs(bag_of_candy[k] - bag_of_candy[k - 2]) ); } } } } } void AssignPermutation(int pos, int msk){ if (pos == 0) return; int taken = trace[pos][msk]; int numbit = __builtin_popcount(taken); vector<int> arr; vector<int> ans; for(int i = 0; i < n; i++){ if (taken & (1 << i)) arr.pb(bag_of_candy[i + 1]); } for(int i = 0; i < numbit; i += 2){ ans.pb(arr[i]); } for(int i = numbit - 1 - !((numbit - 1)&1); i >= 0; i -= 2){ ans.pb(arr[i]); } for(int i = 0; i < Listcycle[pos - 1].size(); i++){ answer[Listcycle[pos - 1][i]] = ans[i]; } AssignPermutation(pos - 1, msk ^ taken); } void solveSubtask2(){ prep(); memset(ok, 0, sizeof(ok)); int numcycle = 0; for(int i = 1; i <= n; i++){ if (ok[i]) continue; vector<int> oneCycle; numcycle++; for(int j = i; !ok[j] ; j = best_friend[j]){ oneCycle.pb(j); ok[j] = 1; } Listcycle.pb(oneCycle); } memset(dp, 0x3f, sizeof(dp)); sort(Listcycle.begin(), Listcycle.end(), [&](const vector<int> &a, const vector<int> &b){ return a.size() > b.size(); }); queue<array<int, 3>> q; q.push({0, 0, 0}); dp[0][0] = 0; int sz = 0; while(!q.empty()){ int du = q.front()[0]; int pos = q.front()[1]; int msk = q.front()[2]; int testmsk = 0; q.pop(); if (du > dp[pos][msk] or pos == (int) Listcycle.size()) continue; int sz = Listcycle[pos].size(); for(int i = 0; i < sz; i++){ testmsk <<= 1; testmsk++; } // cout << sz << ' ' << testmsk << endl; for(int j = 0; j < n + 1 - sz; j++){ if (((testmsk << j) & msk) == 0) { if (minimize(dp[pos + 1][msk ^ (testmsk << j)], max(du, MinDistriRange[j + 1][j + sz]))){ q.push({dp[pos + 1][msk ^ (testmsk << j)], pos + 1, msk ^ (testmsk << j) }); trace[pos + 1][msk ^ (testmsk << j)] = (testmsk << j); } } } } cout << dp[Listcycle.size()][(1 << n) - 1] << endl; AssignPermutation(Listcycle.size(), (1 << n) - 1); for(int i = 1; i <= n; i++){ cout << answer[i] << ' '; } cout << endl; } } namespace subtask3{ int MinDistriRange[MAXN][MAXN], ok[MAXN], answer[MAXN]; vector<vector<int>> Listcycle; map<ii, int> dp; map<ii, int> trace; map<int, bitset<MAXN>> transfer; void prep(){ sort(bag_of_candy + 1, bag_of_candy + 1 + n); for(int i = 1; i <= n; i++){ for(int j = i; j <= n; j++){ int length = j - i + 1; if (length == 1) MinDistriRange[i][j] = 0; else if (length == 2) MinDistriRange[i][j] = abs(bag_of_candy[j] - bag_of_candy[i]); else { for(int k = i + 2; k <= j; k++){ maximize(MinDistriRange[i][j], abs(bag_of_candy[k] - bag_of_candy[k - 2]) ); } } } } } bitset<MAXN> Mask; const int base = 113; int hashBitSet(bitset<MAXN> &b){ int res = 0; for(int i = 0; i < MAXN; i++){ res = (res * base + (b[i] + 1)) % MOD; } transfer[res] = b; return res; } void Assign(int pos, bitset<MAXN> &mask){ if (pos == 0) return; int getcode = hashBitSet(mask); int prvcode = trace[ii(pos, getcode)]; bitset<MAXN> tmp = transfer[prvcode]; bitset<MAXN> taken = mask ^ tmp; vector<int> ans; vector<int> arr; for(int i = 0; i < n; i++){ if (taken[i] == 1) arr.pb(bag_of_candy[i + 1]); } // cout << endl; int numbit = taken.count(); for(int i = 0; i < numbit; i += 2){ ans.pb(arr[i]); } for(int i = numbit - 1 - !((numbit - 1) & 1); i >= 0; i -= 2){ ans.pb(arr[i]); } for(int i = 0; i < Listcycle[pos - 1].size(); i++){ answer[Listcycle[pos - 1][i]] = ans[i]; } mask ^= tmp; Assign(pos - 1, mask); } void solveSubtask3(){ prep(); memset(ok, 0, sizeof(ok)); int numcycle = 0; for(int i = 1; i <= n; i++){ if (ok[i]) continue; vector<int> oneCycle; numcycle++; for(int j = i; !ok[j] ; j = best_friend[j]){ oneCycle.pb(j); ok[j] = 1; } Listcycle.pb(oneCycle); } sort(Listcycle.begin(), Listcycle.end(), [&](const vector<int> &a, const vector<int> &b){ return a.size() > b.size(); }); Mask.reset(); int gethash = hashBitSet(Mask); queue<array<int, 3>> q; bitset<MAXN> testmask; dp[ii(0, gethash)] = 0; q.push({0, 0, gethash}); while(!q.empty()){ int du = q.front()[0]; int pos = q.front()[1]; int hashBIT = q.front()[2]; q.pop(); if (du > dp[ii(pos, hashBIT)] or pos == (int) Listcycle.size()) continue; Mask = transfer[hashBIT]; int sz = Listcycle[pos].size(); for(int i = 0; i < sz; i++){ testmask <<= 1; testmask |= 1; } for(int j = 0; j < n - sz + 1; j++){ if ((Mask & (testmask << j)).count() == 0){ Mask ^= testmask; int newmsk = hashBitSet(Mask); if (dp.find({pos + 1, newmsk}) == dp.end()) dp[ii(pos + 1, newmsk)] = INF; if (minimize(dp[ii(pos + 1, newmsk)], max(du, MinDistriRange[j + 1][j + sz]) )){ trace[ii(pos + 1, newmsk)] = hashBIT; q.push({pos + 1, newmsk}); } Mask ^= testmask; } } } for(int i = 0; i < n; i++){ Mask[i] = 1; } int getcode = hashBitSet(Mask); cout << dp[ii(Listcycle.size(), getcode)] << endl; Assign(Listcycle.size(), Mask); for(int i = 1; i <= n; i++){ cout << answer[i] << ' '; } cout << endl; } } main() { fast; if (fopen(TASKNAME".inp","r")){ freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".out","w",stdout); } cin >> n; for(int i = 1; i <= n; i++){ cin >> best_friend[i]; } for(int i = 1; i <= n; i++){ cin >> bag_of_candy[i]; } // if (subtask1::checkSubtask1()) return subtask1::solveSubtask1(), 0; // if (subtask2::checkSubtask2()) return subtask2::solveSubtask2(), 0; return subtask3::solveSubtask3(), 0; } /** Warning: - MLE / TLE? - Gioi han mang? - Gia tri max phai luon gan cho -INF - long long co can thiet khong? - tran mang. - code can than hon - Nho sinh test de tranh RTE / TLE --> Coi lai truoc khi nop **/

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

vrtic.cpp: In function 'void subtask1::solveSubtask1()':
vrtic.cpp:36:22: warning: unused variable 'splitting_point' [-Wunused-variable]
   36 |         int res = 0, splitting_point = 0;
      |                      ^~~~~~~~~~~~~~~
vrtic.cpp:38:13: warning: unused variable 'cur' [-Wunused-variable]
   38 |         int cur = 0;
      |             ^~~
vrtic.cpp: In function 'void subtask2::AssignPermutation(int, int)':
vrtic.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |          for(int i = 0; i < Listcycle[pos - 1].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
vrtic.cpp: In function 'void subtask2::solveSubtask2()':
vrtic.cpp:125:13: warning: unused variable 'sz' [-Wunused-variable]
  125 |         int sz = 0;
      |             ^~
vrtic.cpp: In function 'void subtask3::Assign(int, std::bitset<159>&)':
vrtic.cpp:214:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |         for(int i = 0; i < Listcycle[pos - 1].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
vrtic.cpp: In function 'void subtask3::solveSubtask3()':
vrtic.cpp:6:13: warning: overflow in conversion from 'double' to 'std::map<std::pair<int, int>, int>::mapped_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | #define INF 1e18
      |             ^~~~
vrtic.cpp:263:91: note: in expansion of macro 'INF'
  263 |                     if (dp.find({pos + 1, newmsk}) == dp.end()) dp[ii(pos + 1, newmsk)] = INF;
      |                                                                                           ^~~
vrtic.cpp: At global scope:
vrtic.cpp:286:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  286 | main()
      | ^~~~
vrtic.cpp: In function 'int main()':
vrtic.cpp:290:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  290 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
vrtic.cpp:291:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  291 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...