제출 #427152

#제출 시각아이디문제언어결과실행 시간메모리
427152dreezyArranging Shoes (IOI19_shoes)C++17
50 / 100
1065 ms3244 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back //n = 1 its either 1 or 0 //n = 8 we can brutazo //all shoes are same, we just need to get all inversion (even is left, odd is right) //all shoes need to travel n? //eta ~ 25 minutes /*full solutions*/ //O(N^2) /* dp[n][i] //min swaps at position i after considering n pairs? */ /*SUBTASK 1, 3, 4*/ /* long long count_swaps(vector<int> s) { ll ans = 0; int n = s.size(); int first = 0; for(int i =0; i<n; i++){ if(s[i] < 0){ ans += abs(i - first); first +=2; } } return ans; } */ /*SUBTASK 2*/ //something is wrong, ill come back to it later //i need to think more long long count_swaps(vector<int> s) { ll ans = 1e18; int n = s.size(); vector<int> lefts(n/2); int cntleft = 0; vector<pair<int, int>> sortlefts(n/2); vector<bool> ava(n, 1); for(int i =0; i<n; i++){ if(s[i] < 0){ lefts[cntleft++] = i; int firstright = -1; for(int j =0; j<n ;j++){ if(ava[j] and s[j] == -s[i]){ ava[j] = false; firstright = j; break; } } sortlefts[cntleft - 1] = {i+firstright, i}; } } sort(sortlefts.begin(), sortlefts.end()); for(int i =0; i<n/2; i++){ lefts[i] = sortlefts[i].second; } //do{ ll posans = 0; vector<bool> available(n, 1); vector<int> inds(n); for(int i =0; i<n ;i++) inds[i] = i; //for(int i =0; i<n/ 2; i++) cout << lefts[i]<<", "; cout <<endl; for(int l =0; l<n/2; l++){ //get first availabe int firstright =-1; for(int i =0; i<n ;i++){ //cout <<s[lefts[l]]<<": "<<s[i]<<' '; if(available[i] and s[i] == -s[lefts[l]]){ firstright = i; available[i] = false; break; } } //cout <<endl; ll dist1 = abs(inds[lefts[l]] - 2 * l); for(int k = 0; k<n ;k++){ if(inds[k] >= 2 * l && inds[k] < inds[lefts[l]]) inds[k]++; } ll dist2 = abs(inds[firstright] -( 2 * l + 1)); for(int k =0;k<n; k++){ if(inds[k] >=2* l + 1 and inds[k] < inds[firstright]) inds[k]++; } //cout << inds[lefts[l]]<<", "<<inds[firstright]<<": "; //cout << lefts[l]<<", "<<firstright<<": "<<dist1<<", "<<dist2<<endl; posans += dist1 + dist2; } ans = min(ans, posans); //cout << posans<<endl<<endl; //}while(next_permutation(lefts.begin(), lefts.end())); return ans; } /***********/
#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...