algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }