2013年8月8日

UVa 12504 - Updating a Dictionary

#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define PB push_back
using namespace std;

void print(char c, vector<string> & v) {
  if (!v.size()) {
    return;
  }
  putchar(c);
  for (int i = 0; i < v.size(); i++) {
    printf("%s%s", v[i].c_str(), i == v.size() - 1 ? "\n" : ",");
  }
}

int main() {
  char s[9999];
  gets(s);
  int T;
  sscanf(s, "%d", &T);
  while (T--) {
    map<string, string> d1, d2;
    string k, v;
    bool rk = true, rv = false;
    gets(s);
    for (int i = 1; s[i]; i++) {
      if (s[i] == ':') {
        rk = false;
        rv = true;
        continue;
      } else if (s[i] == ',' || s[i] == '}') {
        if (k == "" || v == "") {
          continue;
        }
        rk = true;
        rv = false;
        d1[k] = v;
        k = v = "";
        continue;
      }
      if (rk) {
        k.insert(k.end(), s[i]);
      } else {
        v.insert(v.end(), s[i]);
      }
    }
    rk = true;
    rv = false;
    k = v = "";
    vector<string> add, remove, change;
    gets(s);
    for (int i = 1; s[i]; i++) {
      if (s[i] == ':') {
        rk = false;
        rv = true;
        continue;
      } else if (s[i] == ',' || s[i] == '}') {
        rk = true;
        rv = false;
        if (k == "" || v == "") {
          continue;
        }
        d2[k] = v;
        if (d1.count(k)) {
          if (d1[k] != v) {
            change.PB(k);
          }
        } else {
          add.PB(k);
        }
        k = v = "";
        continue;
      }
      if (rk) {
        k.insert(k.end(), s[i]);
      } else {
        v.insert(v.end(), s[i]);
      }
    }
    for (map<string, string>::iterator it = d1.begin(); it != d1.end(); it++) {
      if (!d2.count(it->first)) {
        remove.PB(it->first);
      }
    }
    sort(add.begin(), add.end());
    sort(change.begin(), change.end());

    if (!add.size() && !remove.size() && !change.size()) {
      puts("No changes");
    } else {
      print('+', add);
      print('-', remove);
      print('*', change);
    }

    puts("");
  }
  return 0;
}

沒有留言:

張貼留言