#include <cstdio> #include <vector> using namespace std; int calc_cyc(int money, int diff, int xxx); int main() { int n, m; scanf("%d\n", &n); vector<int> boys(n); for(int i=0; i<n; i++) { scanf("%d ", &boys[i]); } scanf("%d\n", &m); vector<int> wins(m); vector<int> numbers(m); char tmp; for(int i=0; i<m; i++) { numbers[i] = i; scanf("%c", &tmp); if(tmp == 'W') wins[i] = 1; else wins[i] = -1; } vector< vector<int> > cycles; vector<int> empty(3); vector<int> visited(m); for(int i=0; i<m; i++) { if(visited[i] == 0) { cycles.push_back(empty); cycles.back().at(2) = i; visited[i] = 1; int k = 0; while(true) { k = (k+n)%m; if(visited[k]) break; visited[k] = 1; cycles.back().push_back(k); } } } for(int i=0; i<m; i++) { int k = m+i; while(k<n) { if(boys[k] < boys[i]) { boys[i] = boys[k]; numbers[i] = k; } k += m; } } for(int i=0; i<cycles.size(); i++) { for(int j=2; j<cycles[i].size(); j++) { cycles[i].at(0) += wins[cycles[i].at(j)]; } int best = 2, current = 0; for(int j=2; j<cycles[i].size(); j++) { current += wins[cycles[i].at(j)]; if(current > 0 && j<cycles[i].size()-1) { best = j+1; current = 0; } } current = 0; for(int j=best; j<cycles[i].size(); j++) { current += wins[cycles[i].at(j)]; if(current < cycles[i].at(1)) cycles[i].at(1) = current; } for(int j=2; j<best; j++) { current += wins[cycles[i].at(j)]; if(current < cycles[i].at(1)) cycles[i].at(1) = current; } } long long result = -1; for(int i=0; i<cycles.size(); i++) { int nr_cyc = -1; vector<int> which_boys; for(int j=2; j<cycles[i].size(); j++) { if(cycles[i].at(j) >= n) continue; if((calc_cyc(boys[cycles[i].at(j)], cycles[i].at(0), cycles[i].at(1)) < nr_cyc && nr_cyc > 0) || nr_cyc < 0) { nr_cyc = calc_cyc(boys[cycles[i].at(j)], cycles[i].at(0), cycles[i].at(1)); which_boys.clear(); } if(calc_cyc(boys[cycles[i].at(j)], cycles[i].at(0), cycles[i].at(1)) == nr_cyc) which_boys.push_back(j); } if(cycles[i].at(0) >= 0 && nr_cyc != 0) continue; int best_boy = which_boys[0], d = 0, pos = 1; for(int j=best_boy; j<cycles[i].size(); j++) { d += wins[cycles[i].at(j)]; if(pos < which_boys.size() && j+1 == which_boys[pos] && boys[cycles[i].at(j+1)] < boys[cycles[i].at(best_boy)]+d) { best_boy = j+1; pos++; d = 0; } } boys[cycles[i].at(best_boy)] += nr_cyc*cycles[i].at(0); int count = 0; while(boys[cycles[i].at(best_boy)]) { for(int j=best_boy; j<cycles[i].size(); j++) { if(!boys[cycles[i].at(best_boy)]) break; boys[cycles[i].at(best_boy)] += wins[cycles[i].at(j)]; count++; } for(int j=2; j<best_boy; j++) { if(!boys[cycles[i].at(best_boy)]) break; boys[cycles[i].at(best_boy)] += wins[cycles[i].at(j)]; count++; } } if((result > 0 && (nr_cyc*(cycles[i].size()-2)+count)*n+numbers[cycles[i].at(best_boy)] < result) || result < 0) { result = (nr_cyc*(cycles[i].size()-2)+count)*n+numbers[cycles[i].at(best_boy)]; } } if(result > n) result -= n; if(result == -1) result--; printf("%d\n", result+1); return 0; } int calc_cyc(int money, int diff, int xxx) { if(diff < 0) diff *= -1; int k, rest; k = money/diff; rest = money - k*diff; while(rest + diff <= -xxx && rest + diff <= money) { rest += diff; k--; } return k; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | #include <cstdio> #include <vector> using namespace std; int calc_cyc(int money, int diff, int xxx); int main() { int n, m; scanf("%d\n", &n); vector<int> boys(n); for(int i=0; i<n; i++) { scanf("%d ", &boys[i]); } scanf("%d\n", &m); vector<int> wins(m); vector<int> numbers(m); char tmp; for(int i=0; i<m; i++) { numbers[i] = i; scanf("%c", &tmp); if(tmp == 'W') wins[i] = 1; else wins[i] = -1; } vector< vector<int> > cycles; vector<int> empty(3); vector<int> visited(m); for(int i=0; i<m; i++) { if(visited[i] == 0) { cycles.push_back(empty); cycles.back().at(2) = i; visited[i] = 1; int k = 0; while(true) { k = (k+n)%m; if(visited[k]) break; visited[k] = 1; cycles.back().push_back(k); } } } for(int i=0; i<m; i++) { int k = m+i; while(k<n) { if(boys[k] < boys[i]) { boys[i] = boys[k]; numbers[i] = k; } k += m; } } for(int i=0; i<cycles.size(); i++) { for(int j=2; j<cycles[i].size(); j++) { cycles[i].at(0) += wins[cycles[i].at(j)]; } int best = 2, current = 0; for(int j=2; j<cycles[i].size(); j++) { current += wins[cycles[i].at(j)]; if(current > 0 && j<cycles[i].size()-1) { best = j+1; current = 0; } } current = 0; for(int j=best; j<cycles[i].size(); j++) { current += wins[cycles[i].at(j)]; if(current < cycles[i].at(1)) cycles[i].at(1) = current; } for(int j=2; j<best; j++) { current += wins[cycles[i].at(j)]; if(current < cycles[i].at(1)) cycles[i].at(1) = current; } } long long result = -1; for(int i=0; i<cycles.size(); i++) { int nr_cyc = -1; vector<int> which_boys; for(int j=2; j<cycles[i].size(); j++) { if(cycles[i].at(j) >= n) continue; if((calc_cyc(boys[cycles[i].at(j)], cycles[i].at(0), cycles[i].at(1)) < nr_cyc && nr_cyc > 0) || nr_cyc < 0) { nr_cyc = calc_cyc(boys[cycles[i].at(j)], cycles[i].at(0), cycles[i].at(1)); which_boys.clear(); } if(calc_cyc(boys[cycles[i].at(j)], cycles[i].at(0), cycles[i].at(1)) == nr_cyc) which_boys.push_back(j); } if(cycles[i].at(0) >= 0 && nr_cyc != 0) continue; int best_boy = which_boys[0], d = 0, pos = 1; for(int j=best_boy; j<cycles[i].size(); j++) { d += wins[cycles[i].at(j)]; if(pos < which_boys.size() && j+1 == which_boys[pos] && boys[cycles[i].at(j+1)] < boys[cycles[i].at(best_boy)]+d) { best_boy = j+1; pos++; d = 0; } } boys[cycles[i].at(best_boy)] += nr_cyc*cycles[i].at(0); int count = 0; while(boys[cycles[i].at(best_boy)]) { for(int j=best_boy; j<cycles[i].size(); j++) { if(!boys[cycles[i].at(best_boy)]) break; boys[cycles[i].at(best_boy)] += wins[cycles[i].at(j)]; count++; } for(int j=2; j<best_boy; j++) { if(!boys[cycles[i].at(best_boy)]) break; boys[cycles[i].at(best_boy)] += wins[cycles[i].at(j)]; count++; } } if((result > 0 && (nr_cyc*(cycles[i].size()-2)+count)*n+numbers[cycles[i].at(best_boy)] < result) || result < 0) { result = (nr_cyc*(cycles[i].size()-2)+count)*n+numbers[cycles[i].at(best_boy)]; } } if(result > n) result -= n; if(result == -1) result--; printf("%d\n", result+1); return 0; } int calc_cyc(int money, int diff, int xxx) { if(diff < 0) diff *= -1; int k, rest; k = money/diff; rest = money - k*diff; while(rest + diff <= -xxx && rest + diff <= money) { rest += diff; k--; } return k; } |