// Potyczki Algorytmiczne 2015 // runda 3 // HAZard // Tomasz Pastusiak #include <iostream> #include <algorithm> #include <functional> #include <stack> #include <set> #include <cmath> #include <vector> #include <string> using namespace std; #define MAX_M_N 1000000 //#define MAX_M_N 999999 #define MAX_SECTIONS 30 #define LL long long int //#define MAX_M_N 4 //#define MAX_SECTIONS 30 int savings[MAX_M_N]; int cycle[MAX_M_N]; pair<int, int> cycleInfo[MAX_M_N]; // <cycleID, startingPointInCycle> pair<int, int> individualCyclesAttributes[MAX_M_N]; // <starting point in mt, base(not doubled) length in mt> LL playerDuration[MAX_M_N]; // store how long a player can handle int baseSections[MAX_SECTIONS]; int baseSectionsRight[MAX_SECTIONS]; class MinTree{ public: int tree[MAX_M_N*2*2]; // every cycle will be written doubled, thus * 2 int n; int size; void setSize(int n){ this->n = n; size = 2*n; for(int i=1;i<size;++i){ tree[i] = 2*MAX_M_N; // to be safe } } void setValue(int position, int value){ int node = n + position; tree[node] = value; while (node != 1) { node /= 2; if(tree[node] > value) tree[node] = value; else break; } } int getValue(int position){ int node = n + position; return tree[node]; } int getAreaMin(int from, int to){ int nl = n + from, nr = n + to; // node left, node right int result = min(tree[nl], tree[nr]); while (nl / 2 != nr / 2) { if (nl % 2 == 0){ result = min(result, tree[nl + 1]); } // if left node is left child of some parent if (nr % 2 == 1){ result = min(result, tree[nr - 1]); } // if right node is right child of some parent nl /= 2; nr /= 2; } return result; } int pfflleqt(int from, int to, int value){ int nl = n + from, nr = n + to; // node left, node right int sectionsCountLeft = 1; int sectionsCountRight = 1; int sectionsCount = 0; baseSections[0] = nl; baseSectionsRight[0] = nr; while (nl / 2 != nr / 2) { if (nl % 2 == 0){ baseSections[sectionsCountLeft++] = nl + 1; } // if left node is left child of some parent if (nr % 2 == 1){ baseSectionsRight[sectionsCountRight++] = nr - 1; } // if right node is right child of some parent nl /= 2; nr /= 2; } sectionsCount = sectionsCountLeft; for(int i= sectionsCountRight - 1; i >= 0 ; --i){ baseSections[sectionsCount++] = baseSectionsRight[i]; } // Sections Obtained, int result = -1; for(int i=0; i<sectionsCount; ++i){ if(tree[baseSections[i]] <= value){ int node = baseSections[i]; while(node < n){ int leftSon = 2*node; int rightSon = leftSon + 1; if( tree[leftSon] <= value ) node = leftSon; // prefer left son else node = rightSon; } // while not at ground level result = node - n; break; } // if section found, dig deeper } return result; } // pfflleqt - Position First From Left Lower or Equal Than }; MinTree mt; int main(){ ios_base::sync_with_stdio(false); int n, m; cin >> n; for(int i=0; i<n;++i){ cin >> savings[i]; playerDuration[i] = 0; // no need to initialise... in fact } cin >> m; string buffer; buffer.reserve(MAX_M_N); cin >> buffer; for(int i=0; i<m; ++i){ cycle[i] = (buffer[i] == 'W' ? 1 : -1); cycleInfo[i] = make_pair(-1, -1); } int placeInMTtaken = 0; mt.setSize(2*m); for(int i=0; i<n; ++i){ if(cycleInfo[i%m].first == -1){ int positionInIC = 0; int positionInCycle = i%m; int currentPlayer = i; int IC_ID = i; int partialSum = 0; individualCyclesAttributes[IC_ID] = make_pair(placeInMTtaken, 1); // cycle length has to be updated later, after we find full cycle while(cycleInfo[positionInCycle].first == -1){ cycleInfo[positionInCycle] = make_pair(IC_ID, positionInIC++); partialSum += cycle[positionInCycle]; mt.setValue(placeInMTtaken++, partialSum); positionInCycle += n; positionInCycle %= m; } // // cycle written to MT once, TODO write it again int IC_length = positionInIC; for(int j=0; j<IC_length ;++j){ partialSum += cycle[positionInCycle]; mt.setValue(placeInMTtaken++, partialSum); positionInCycle += n; positionInCycle %= m; } // previous while loop ended, because we arrived at the beginning of IC, so we can now loop through IC again, adding it to MT again individualCyclesAttributes[IC_ID].second = IC_length; } // if there is a player without a cycle, start a individual cycle here } // traverse machine cycle, looking for individual cycles /*for(int i=0;i<n;++i){ cout << "Player: " << i << " cycle ID: " << cycleInfo[i%m].first << " starting point: " << cycleInfo[i%m].second << " Cycle len: " << individualCyclesAttributes[cycleInfo[i%m].first].second << endl; } cout << "--------" << endl;*/ /**for(int i=0;i<m;++i){ cout << "Cycle position: " << i << " starting point: " << cycleInfo[i].second << " Cycle len: " << individualCyclesAttributes[cycleInfo[i].first].second << endl; }*/ for(int i=0; i<n ;++i){ pair<int, int> cycleInfoForPlayer = cycleInfo[i%m]; // <cycleID, startingPointInCycle> pair<int, int> cycleAttributes = individualCyclesAttributes[cycleInfoForPlayer.first]; // <starting point in mt, base(not doubled) length in mt> int MTstart = cycleAttributes.first + cycleInfoForPlayer.second; int MTend = MTstart + cycleAttributes.second - 1; // <start, end> sharp braces ! int partialSumRelative = 0; if(cycleInfoForPlayer.second != 0){ partialSumRelative = -mt.getValue(MTstart - 1); } int ICs_passed = 0; int worstSituation = partialSumRelative + mt.getAreaMin(MTstart, MTend); int IC_balance = partialSumRelative + mt.getValue(MTend); int moneyDistFromBankrupcy = savings[i] + worstSituation; if(IC_balance >= 0 && moneyDistFromBankrupcy > 0){ playerDuration[i] = -1; // infinite duration } else{ if(moneyDistFromBankrupcy > 0){ int ICs_leftToBankrupcy = moneyDistFromBankrupcy/(-IC_balance); if(ICs_leftToBankrupcy * (-IC_balance) != moneyDistFromBankrupcy) ICs_leftToBankrupcy++; // these two lines should work like ceil ICs_passed = ICs_leftToBankrupcy; partialSumRelative += IC_balance*ICs_passed; } // if we are not bankrupt yet, fast forward int bankrupcyMoment = mt.pfflleqt(MTstart, MTend, -savings[i] - partialSumRelative) - MTstart; playerDuration[i] = i + ICs_passed*(LL)cycleAttributes.second*(LL)n + bankrupcyMoment*(LL)n + 1; // i players before me, (ICs_passed*cycleLen) times all players played before me, ... // use long longs here? } // else, we are going bankrupt, but when? } // for each player, calculate duration LL smallestDuration = -1; for(int i=0; i<n; ++i){ if(smallestDuration == -1) smallestDuration = playerDuration[i]; else if(playerDuration[i] != -1) smallestDuration = min(smallestDuration, playerDuration[i]); } cout << smallestDuration << endl; return 0; }
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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 | // Potyczki Algorytmiczne 2015 // runda 3 // HAZard // Tomasz Pastusiak #include <iostream> #include <algorithm> #include <functional> #include <stack> #include <set> #include <cmath> #include <vector> #include <string> using namespace std; #define MAX_M_N 1000000 //#define MAX_M_N 999999 #define MAX_SECTIONS 30 #define LL long long int //#define MAX_M_N 4 //#define MAX_SECTIONS 30 int savings[MAX_M_N]; int cycle[MAX_M_N]; pair<int, int> cycleInfo[MAX_M_N]; // <cycleID, startingPointInCycle> pair<int, int> individualCyclesAttributes[MAX_M_N]; // <starting point in mt, base(not doubled) length in mt> LL playerDuration[MAX_M_N]; // store how long a player can handle int baseSections[MAX_SECTIONS]; int baseSectionsRight[MAX_SECTIONS]; class MinTree{ public: int tree[MAX_M_N*2*2]; // every cycle will be written doubled, thus * 2 int n; int size; void setSize(int n){ this->n = n; size = 2*n; for(int i=1;i<size;++i){ tree[i] = 2*MAX_M_N; // to be safe } } void setValue(int position, int value){ int node = n + position; tree[node] = value; while (node != 1) { node /= 2; if(tree[node] > value) tree[node] = value; else break; } } int getValue(int position){ int node = n + position; return tree[node]; } int getAreaMin(int from, int to){ int nl = n + from, nr = n + to; // node left, node right int result = min(tree[nl], tree[nr]); while (nl / 2 != nr / 2) { if (nl % 2 == 0){ result = min(result, tree[nl + 1]); } // if left node is left child of some parent if (nr % 2 == 1){ result = min(result, tree[nr - 1]); } // if right node is right child of some parent nl /= 2; nr /= 2; } return result; } int pfflleqt(int from, int to, int value){ int nl = n + from, nr = n + to; // node left, node right int sectionsCountLeft = 1; int sectionsCountRight = 1; int sectionsCount = 0; baseSections[0] = nl; baseSectionsRight[0] = nr; while (nl / 2 != nr / 2) { if (nl % 2 == 0){ baseSections[sectionsCountLeft++] = nl + 1; } // if left node is left child of some parent if (nr % 2 == 1){ baseSectionsRight[sectionsCountRight++] = nr - 1; } // if right node is right child of some parent nl /= 2; nr /= 2; } sectionsCount = sectionsCountLeft; for(int i= sectionsCountRight - 1; i >= 0 ; --i){ baseSections[sectionsCount++] = baseSectionsRight[i]; } // Sections Obtained, int result = -1; for(int i=0; i<sectionsCount; ++i){ if(tree[baseSections[i]] <= value){ int node = baseSections[i]; while(node < n){ int leftSon = 2*node; int rightSon = leftSon + 1; if( tree[leftSon] <= value ) node = leftSon; // prefer left son else node = rightSon; } // while not at ground level result = node - n; break; } // if section found, dig deeper } return result; } // pfflleqt - Position First From Left Lower or Equal Than }; MinTree mt; int main(){ ios_base::sync_with_stdio(false); int n, m; cin >> n; for(int i=0; i<n;++i){ cin >> savings[i]; playerDuration[i] = 0; // no need to initialise... in fact } cin >> m; string buffer; buffer.reserve(MAX_M_N); cin >> buffer; for(int i=0; i<m; ++i){ cycle[i] = (buffer[i] == 'W' ? 1 : -1); cycleInfo[i] = make_pair(-1, -1); } int placeInMTtaken = 0; mt.setSize(2*m); for(int i=0; i<n; ++i){ if(cycleInfo[i%m].first == -1){ int positionInIC = 0; int positionInCycle = i%m; int currentPlayer = i; int IC_ID = i; int partialSum = 0; individualCyclesAttributes[IC_ID] = make_pair(placeInMTtaken, 1); // cycle length has to be updated later, after we find full cycle while(cycleInfo[positionInCycle].first == -1){ cycleInfo[positionInCycle] = make_pair(IC_ID, positionInIC++); partialSum += cycle[positionInCycle]; mt.setValue(placeInMTtaken++, partialSum); positionInCycle += n; positionInCycle %= m; } // // cycle written to MT once, TODO write it again int IC_length = positionInIC; for(int j=0; j<IC_length ;++j){ partialSum += cycle[positionInCycle]; mt.setValue(placeInMTtaken++, partialSum); positionInCycle += n; positionInCycle %= m; } // previous while loop ended, because we arrived at the beginning of IC, so we can now loop through IC again, adding it to MT again individualCyclesAttributes[IC_ID].second = IC_length; } // if there is a player without a cycle, start a individual cycle here } // traverse machine cycle, looking for individual cycles /*for(int i=0;i<n;++i){ cout << "Player: " << i << " cycle ID: " << cycleInfo[i%m].first << " starting point: " << cycleInfo[i%m].second << " Cycle len: " << individualCyclesAttributes[cycleInfo[i%m].first].second << endl; } cout << "--------" << endl;*/ /**for(int i=0;i<m;++i){ cout << "Cycle position: " << i << " starting point: " << cycleInfo[i].second << " Cycle len: " << individualCyclesAttributes[cycleInfo[i].first].second << endl; }*/ for(int i=0; i<n ;++i){ pair<int, int> cycleInfoForPlayer = cycleInfo[i%m]; // <cycleID, startingPointInCycle> pair<int, int> cycleAttributes = individualCyclesAttributes[cycleInfoForPlayer.first]; // <starting point in mt, base(not doubled) length in mt> int MTstart = cycleAttributes.first + cycleInfoForPlayer.second; int MTend = MTstart + cycleAttributes.second - 1; // <start, end> sharp braces ! int partialSumRelative = 0; if(cycleInfoForPlayer.second != 0){ partialSumRelative = -mt.getValue(MTstart - 1); } int ICs_passed = 0; int worstSituation = partialSumRelative + mt.getAreaMin(MTstart, MTend); int IC_balance = partialSumRelative + mt.getValue(MTend); int moneyDistFromBankrupcy = savings[i] + worstSituation; if(IC_balance >= 0 && moneyDistFromBankrupcy > 0){ playerDuration[i] = -1; // infinite duration } else{ if(moneyDistFromBankrupcy > 0){ int ICs_leftToBankrupcy = moneyDistFromBankrupcy/(-IC_balance); if(ICs_leftToBankrupcy * (-IC_balance) != moneyDistFromBankrupcy) ICs_leftToBankrupcy++; // these two lines should work like ceil ICs_passed = ICs_leftToBankrupcy; partialSumRelative += IC_balance*ICs_passed; } // if we are not bankrupt yet, fast forward int bankrupcyMoment = mt.pfflleqt(MTstart, MTend, -savings[i] - partialSumRelative) - MTstart; playerDuration[i] = i + ICs_passed*(LL)cycleAttributes.second*(LL)n + bankrupcyMoment*(LL)n + 1; // i players before me, (ICs_passed*cycleLen) times all players played before me, ... // use long longs here? } // else, we are going bankrupt, but when? } // for each player, calculate duration LL smallestDuration = -1; for(int i=0; i<n; ++i){ if(smallestDuration == -1) smallestDuration = playerDuration[i]; else if(playerDuration[i] != -1) smallestDuration = min(smallestDuration, playerDuration[i]); } cout << smallestDuration << endl; return 0; } |