Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8.
Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
#include <iostream> #include <set> using namespace std; int main() { ios_base::sync_with_stdio(0); int t; cin>>t; for (int l = 0; l < t; l++) { int n; cin>>n; string s; cin>>s; multiset<int> jed; multiset<int> dwa; int pocz = 0; int kon = 0; while (kon < s.length()) { while (pocz < s.length() && s[pocz] == '1') { pocz++; } if (pocz == s.length()) break; kon = pocz; while (kon < s.length() && s[kon] == '0') { kon++; } //err<<pocz<<"-"<<kon<<endl; if (pocz == 0 || kon == s.length() // skrajny przedzia� traci tylko 1 dziennie || kon - pocz == 1) { // jednoelementowe przedzia�y otoczone z dw�ch stron trac� tylko po 1 dziennie jed.insert(kon - pocz); //err<<"jed insert "<<jed.size()<<endl; } else { dwa.insert(kon - pocz); //err<<"dwa insert "<<dwa.size()<<endl; } pocz = kon; } ////err<<" jed size = "<<jed.size()<<" dwa size = "<<dwa.size()<<endl; int dni = 0; // tyle razy ju� zaszczepiono = tyle razy wirus si� rozprzestrzeni� int ocalone = 0; while (!(jed.empty() && dwa.empty())) { //err<<"jedynki\n"; //wypisz(jed, dni); //err<<"dwojki\n"; //wypisz(dwa, 2 * dni); if (jed.empty()) { //err<<"BIORE Z DWA\n"; int pierw = *(--dwa.end()); dwa.erase(--dwa.end()); jed.insert(pierw - dni - 1); ocalone++; } else if (dwa.empty()) { //err<<"BIORE Z JED\n"; int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy //err<<"rozm = "<<rozm<<endl; ocalone += rozm; jed.erase(--jed.end()); } else { //if (*(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni || *(dwa.rbegin()) - 2 * dni <= 3) { //if (*(jed.rbegin()) - dni > 1) { //if (jed.size() > 1 && *(--jed.end()) - dni + *(--(--jed.end())) - dni - 1 > *(--dwa.end()) - 2 * dni - 1) { //if ((jed.size() > 1 && *(--jed.end()) + *(--(--jed.end())) > *(--dwa.end())) || *(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni) { if (2 * (*(jed.rbegin()) - dni) >= *(dwa.rbegin()) - 2 * dni) { //err<<"BIORE Z JED\n"; int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy //err<<"rozm = "<<rozm<<endl; ocalone += rozm; jed.erase(--jed.end()); } else { //err<<"BIORE Z DWA\n"; int pierw = *(--dwa.end()); dwa.erase(--dwa.end()); jed.insert(pierw - dni - 1); ocalone++; } } dni++; // wirus si� rozprzestrzenia // usuwamy te, kt�re po rozprzestrznieniu nie b�d� istnie� /* for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni; it++) { // aktualny rozmiar 0 dwa.erase(it); }*/ dwa.erase(2 * dni); // (2 * dni - 1) zosta�o wcze�niej przeczucone do jed /* for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni + 1; it++) { // aktualny rozmiar 1 dwa.erase(it); jed.insert(*it - dni); }*/ int ile = dwa.count(2 * dni + 1); dwa.erase(2 * dni + 1); for (int j = 0; j < ile; j++) { jed.insert(dni + 1); } /* for (set<int>::iterator it = jed.begin(); it != jed.end() && *it <= dni; it++) { jed.erase(it); }*/ jed.erase(dni); } //err<<"ocalone "<<ocalone<<endl; cout<<n - ocalone<<"\n"; } }
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 | #include <iostream> #include <set> using namespace std; int main() { ios_base::sync_with_stdio(0); int t; cin>>t; for (int l = 0; l < t; l++) { int n; cin>>n; string s; cin>>s; multiset<int> jed; multiset<int> dwa; int pocz = 0; int kon = 0; while (kon < s.length()) { while (pocz < s.length() && s[pocz] == '1') { pocz++; } if (pocz == s.length()) break; kon = pocz; while (kon < s.length() && s[kon] == '0') { kon++; } //err<<pocz<<"-"<<kon<<endl; if (pocz == 0 || kon == s.length() // skrajny przedzia� traci tylko 1 dziennie || kon - pocz == 1) { // jednoelementowe przedzia�y otoczone z dw�ch stron trac� tylko po 1 dziennie jed.insert(kon - pocz); //err<<"jed insert "<<jed.size()<<endl; } else { dwa.insert(kon - pocz); //err<<"dwa insert "<<dwa.size()<<endl; } pocz = kon; } ////err<<" jed size = "<<jed.size()<<" dwa size = "<<dwa.size()<<endl; int dni = 0; // tyle razy ju� zaszczepiono = tyle razy wirus si� rozprzestrzeni� int ocalone = 0; while (!(jed.empty() && dwa.empty())) { //err<<"jedynki\n"; //wypisz(jed, dni); //err<<"dwojki\n"; //wypisz(dwa, 2 * dni); if (jed.empty()) { //err<<"BIORE Z DWA\n"; int pierw = *(--dwa.end()); dwa.erase(--dwa.end()); jed.insert(pierw - dni - 1); ocalone++; } else if (dwa.empty()) { //err<<"BIORE Z JED\n"; int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy //err<<"rozm = "<<rozm<<endl; ocalone += rozm; jed.erase(--jed.end()); } else { //if (*(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni || *(dwa.rbegin()) - 2 * dni <= 3) { //if (*(jed.rbegin()) - dni > 1) { //if (jed.size() > 1 && *(--jed.end()) - dni + *(--(--jed.end())) - dni - 1 > *(--dwa.end()) - 2 * dni - 1) { //if ((jed.size() > 1 && *(--jed.end()) + *(--(--jed.end())) > *(--dwa.end())) || *(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni) { if (2 * (*(jed.rbegin()) - dni) >= *(dwa.rbegin()) - 2 * dni) { //err<<"BIORE Z JED\n"; int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy //err<<"rozm = "<<rozm<<endl; ocalone += rozm; jed.erase(--jed.end()); } else { //err<<"BIORE Z DWA\n"; int pierw = *(--dwa.end()); dwa.erase(--dwa.end()); jed.insert(pierw - dni - 1); ocalone++; } } dni++; // wirus si� rozprzestrzenia // usuwamy te, kt�re po rozprzestrznieniu nie b�d� istnie� /* for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni; it++) { // aktualny rozmiar 0 dwa.erase(it); }*/ dwa.erase(2 * dni); // (2 * dni - 1) zosta�o wcze�niej przeczucone do jed /* for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni + 1; it++) { // aktualny rozmiar 1 dwa.erase(it); jed.insert(*it - dni); }*/ int ile = dwa.count(2 * dni + 1); dwa.erase(2 * dni + 1); for (int j = 0; j < ile; j++) { jed.insert(dni + 1); } /* for (set<int>::iterator it = jed.begin(); it != jed.end() && *it <= dni; it++) { jed.erase(it); }*/ jed.erase(dni); } //err<<"ocalone "<<ocalone<<endl; cout<<n - ocalone<<"\n"; } } |