acc.cpp (3380B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 // cards from 1 -> n 12 // smallest to largest arrangement 13 // 1 on top, n at bottom 14 // k actions on the deck 15 // 0. remove top card 16 // 1. remove bottom card 17 // 2. remove either top or bottom card 18 // determine the fate of each card 19 // remains in deck 20 // removed from deck 21 // can be both 22 23 24 // n = 4 k = 2 25 26 // 01 27 28 // cards: 1,2,3,4 29 // remove top 30 // remove bottom 31 // 2,3 32 // -,+,+,- 33 34 35 // n = 3, k = 2 36 // 22 37 // 1 2 3 38 // ? + ? 39 // ? ? ? 40 41 // NTS: Worth doing the +-? encoding from the start then considering cases 42 // case: the second option will result in a card being removed, so if only one option remains, that card will be drawn 43 // ugghhhh.... if I do 2 for every character they are all removed 44 // if I do all -1 then we only know one or two of the centermost haven't been removed, depending on the parity of the size 45 // actually it's not that complicated, if we have all ?'s then they have all been taken 46 // otherwise, we don't know if they've been taken because there could be alternative selections that just so happen to have not taken our current one 47 48 // n = 1, k = 1 49 // 2 50 // + 51 // - 52 53 54 // 7 5 55 // 01201 56 57 // +++++++ 58 // -++++++ 59 // -+++++- 60 // -?+++?- 61 // --?++?- 62 // --?+?-- 63 64 void printLs(vector<char>& ls) { 65 for(int i = 0; i < ls.size(); ++i) { 66 cout << ls[i]; 67 } 68 cout << endl; 69 } 70 71 int main() { 72 73 int testCases, n,k; 74 cin >> testCases; 75 76 for(int z = 0; z < testCases; ++z) { 77 cin >> n; 78 cin >> k; 79 vector<char> ls {}; 80 for(int i = 0; i < n; ++i) { 81 ls.push_back('+'); 82 } 83 84 string instructions = ""; 85 cin >> instructions; 86 87 int leftPtr = 0; 88 int rightPtr = ls.size() - 1; 89 int questionCount = 0; 90 91 for(int i = 0; i < instructions.size(); ++i) { 92 93 char inst = instructions[i]; 94 bool handleQuestion = false; 95 bool incCount = false; 96 97 if(inst == '2') { 98 handleQuestion = true; 99 incCount = true; 100 } 101 if(inst == '0') { 102 if(ls[leftPtr] == '?') { 103 handleQuestion = true; 104 } 105 ls[leftPtr] = '-'; // todo: shift questions 106 leftPtr += 1; 107 } 108 else if(inst == '1') { 109 if(ls[rightPtr] == '?') { 110 handleQuestion = true; 111 } 112 ls[rightPtr] = '-'; // todo: shift questions 113 rightPtr -= 1; 114 } 115 116 if(handleQuestion) { 117 if (leftPtr + questionCount + incCount > rightPtr) { 118 for(int m = 0; m < ls.size(); ++m) { 119 ls[m] = '-'; 120 } 121 break; 122 } 123 if(incCount) { 124 ls[leftPtr + questionCount] = '?'; 125 ls[rightPtr - questionCount] = '?'; 126 questionCount += 1; 127 } else if(inst == '0') { 128 ls[leftPtr + questionCount - 1] = '?'; 129 } else { 130 ls[rightPtr - questionCount + 1] = '?'; 131 } 132 } 133 } 134 135 printLs(ls); 136 } 137 }