ICPC 2016 Tsukuba

D.cpp

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
#define int long long
int MOD = 2305266692540551LL;
int BASE = 4001;
signed main() {
  ios::sync_with_stdio(false);
  string S, T; cin >> S >> T;
  if(S.size() < T.size()) swap(S, T);
  int alpha[26];
  alpha[0] = 1;
  for(int i = 1; i < 26; ++i) {
    alpha[i] = (alpha[i - 1] * BASE) % MOD;
  }
  for(int l = (int)T.size(); l >= 1; --l) {
    unordered_set<int> u;
    int hash;
    hash = 0;
    REP(i,l-1) {
      hash += alpha[T[i] - 'a'];
      hash %= MOD;
    }
    // cerr << T.substr(0, l) << " => " << hash << endl;
    for(int i = 0; i < (int)T.size() - l + 1; ++i) {
      hash += alpha[T[i - 1 + l] - 'a'];
      hash %= MOD;
      u.insert(hash);
      // cerr << T.substr(i, l) << " => " << hash << endl;
      hash -= alpha[T[i] - 'a'];
      if(hash < 0) hash += MOD;
    }
 
    hash = 0;
    REP(i,l-1) {
      hash += alpha[S[i] - 'a'];
      hash %= MOD;
    }
    // cerr << S.substr(0, l) << " => " << hash << endl;
    for(int i = 0; i < (int)S.size() - l + 1; ++i) {
      hash += alpha[S[i - 1 + l] - 'a'];
      hash %= MOD;
      // cerr << S.substr(i, l) << " => " << hash << endl;
      if(u.count(hash)) {
        cout << l << endl;
        return 0;
      }
      hash -= alpha[S[i] - 'a'];
      if(hash < 0) hash += MOD;
    }
  }
  cout << 0 << endl;
  return 0;
}

E.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
pair<string, string> split(const string &s) {
  int p = s.find('=');
  string l = s.substr(0, p);
  string r = s.substr(p + 1);
  return make_pair(l, r);
}
bool check(const string &s) {
  int p = s.find('=');
  if(p == -1) return false;
  pair<string, string> sp = split(s);
  if(sp.first.size() == 0 || sp.second.size() == 0) return false;
  int k = 0;
  for(char c : sp.first) {
    if(c == '(') ++k;
    if(c == ')') --k;
    if(k < 0) return false;
  }
  if(k != 0) return false;
  for(char c : sp.second) {
    if(c == '(') ++k;
    if(c == ')') --k;
    if(k < 0) return false;
  }
  return true;
}
typedef string::const_iterator iter;
struct Result {
  bool valid;
  int value;
  Result(bool valid_, int value_) : valid(valid_), value(value_) {}
};
Result fail(false, 114514);
bool Q(iter &p);
Result E(iter &p);
Result T(iter &p);
Result F(iter &p);
Result N(iter &p);
Result B(iter &p);
bool Q(iter &p) {
  Result l = E(p);
  // if(!l.valid) {
  //   cerr << "l = No" << endl;
  // }
  // else {
  //   cerr << "l = " << l.value << endl;
  // }
  if(!l.valid) return false;
  if(*p != '=') return false;
  ++p;
  Result r = E(p);
  // if(!l.valid) {
  //   cerr << "r = No" << endl;
  // }
  // else {
  //   cerr << "r = " << r.value << endl;
  // }
  if(!r.valid) return false;
  if(*p != '\0') return false;
  return l.value == r.value;
}
Result E(iter &p) {
  Result t = T(p);
  if(!t.valid) return fail;
  while(true) {
    if(*p == '+') {
      ++p;
      Result s = T(p);
      if(!s.valid) return fail;
      t.value += s.value;
    }
    else if(*p == '-') {
      ++p;
      Result s = T(p);
      if(!s.valid) return fail;
      t.value -= s.value;
    }
    else {
      break;
    }
  }
  return t;
}
Result T(iter &p) {
  Result t = F(p);
  if(!t.valid) return fail;
  while(true) {
    if(*p == '*') {
      ++p;
      Result s = F(p);
      if(!s.valid) return fail;
      t.value *= s.value;
    }
    else {
      break;
    }
  }
  return t;
}
Result F(iter &p) {
  if(*p == '(') {
    ++p;
    Result e = E(p);
    if(*p != ')') {
      return fail;
    }
    ++p;
    return e;
  }
  else if(*p == '-') {
    ++p;
    Result e = F(p);
    if(!e.valid) return fail;
    e.value *= -1;
    return e;
  }
  return N(p);
}
Result N(iter &p) {
  if(!isdigit(*p)) {
    return fail;
  }
  int n = 0;
  int i = 0;
  while(isdigit(*p)) {
    n *= 2;
    if(i > 0 && n == 0) return fail;
    n += *p - '0';
    ++p;
    ++i;
  }
  // DEBUG(n);
  return Result(true, n);
}
void dbg() {
  string S; cin >> S;
  iter p = S.cbegin();
  bool r = Q(p);
  cout << (r ? "Yes" : "No") << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  if(false) {
    dbg();
  }
  else {
    string S; cin >> S;
    vector<char> ch;
    string ops = "01+-*=()";
    sort(ops.begin(), ops.end());
    REP(i,S.size()) {
      if(ops.find(S[i]) == string::npos) {
        ch.push_back(S[i]);
      }
    }
    sort(ch.begin(), ch.end());
    ch.erase(unique(ch.begin(), ch.end()), ch.end());
    if(ch.size() > 8) {
      cout << 0 << endl;
      return 0;
    }
    map<char, int> replacer;
    REP(i,ch.size()) {
      replacer[ch[i]] = i;
      // DEBUG(ch[i]);
    }
    set<string> ans;
    do {
      string T = S;
      REP(i,T.size()) {
        if(replacer.count(T[i])) T[i] = ops[replacer[T[i]]];
      }
      // if(T == "-0=(0)") DEBUG(T);
      iter p = T.cbegin();
      bool r = Q(p);
      if(r) {
        ans.insert(ops.substr(0,ch.size()));
        // DEBUG(T);
      }
    } while(next_permutation(ops.begin(), ops.end()));
    cout << ans.size() << endl;
  }
}

G.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
const int sqrtN = 700;
// const int sqrtN = 1;
struct SqrtDecomposition {
  int N, K;
  vector<bool> data;
  // 0, 1, -1 (unknown)
  vector<char> reader;
  vector<char> writer;
  SqrtDecomposition(int n) : N(n) {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(K * sqrtN, false);
    reader.assign(K, 0);
    writer.assign(K, -1);
  }
  void set1(int x) {
    int k = x / sqrtN;
    int l = k * sqrtN, r = (k + 1) * sqrtN;
    if(writer[k] != -1) {
      for(int i = l; i < r; ++i) {
        data[i] = writer[k];
      }
    }
    writer[k] = -1;
    data[x] = 1;
    bool all0 = true, all1 = true;
    for(int i = l; i < r; ++i) {
      if(data[i] == 1) all0 = false;
      else all1 = false;
    }
    if(all0) {
      reader[k] = 0;
    }
    else if(all1) {
      reader[k] = 1;
    }
    else {
      reader[k] = -1;
    }
  }
  void set0range(int a, int b) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        writer[k] = 0;
        reader[k] = 0;
      }
      else {
        if(writer[k] != -1) {
          for(int i = l; i < r; ++i) {
            data[i] = writer[k];
          }
        }
        writer[k] = -1;
        for(int i = max(a, l); i < min(b, r); ++i) {
          data[i] = 0;
        }
        bool all0 = true, all1 = true;
        for(int i = l; i < r; ++i) {
          if(data[i] == 1) all0 = false;
          else all1 = false;
        }
        if(all0) {
          reader[k] = 0;
        }
        else if(all1) {
          reader[k] = 1;
        }
        else {
          reader[k] = -1;
        }
      }
    }
  }
  int search(int x) {
    for(int k = x / sqrtN; k >= 0; --k) {
      // DEBUG(k);
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      // DEBUG(l);
      // DEBUG(r);
      if(reader[k] == 1) continue;
      else if(reader[k] == 0) return min(x, r - 1);
      else {
        for(int i = min(r - 1, x); i >= l; --i) {
          // cerr << "data[" << i << "] = " << data[i] << endl;
          if(data[i] == 0) return i;
        }
      }
    }
    return -1;
  }
  bool check0(int x) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= x) continue;
      if(x <= l) {
        if(reader[k] != 0) return false;
      }
      else {
        for(int i = max(x, l); i < r; ++i) {
          if(data[i] != 0) return false;
        }
      }
    }
    return true;
  }
  void dump() {
    cerr << "data[] =";
    REP(i,N) {
      cerr << " " << (int)data[i];
    }
    cerr << endl;
 
    cerr << "reader[] =";
    REP(i,K) {
      cerr << " " << (int)reader[i];
    }
    cerr << endl;
 
    cerr << "writer[] =";
    REP(i,K) {
      cerr << " " << (int)writer[i];
    }
    cerr << endl;
  }
};
void dbg() {
  SqrtDecomposition decomp(10);
  DEBUG(decomp.search(2));
  decomp.set1(2);
  decomp.set0range(3, 3);
  decomp.dump();
 
  DEBUG(decomp.search(3));
  decomp.set1(3);
  decomp.set0range(4, 4);
  decomp.dump();
 
  DEBUG(decomp.search(1));
  decomp.set1(1);
  decomp.set0range(2, 2);
  decomp.dump();
 
  DEBUG(decomp.search(1));
  decomp.dump();
  DEBUG(decomp.check0(1));
  // decomp.set1(1);
}
signed main() {
  if(false) {
    dbg();
  }
  else {
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> query(N);
    REP(i,N) cin >> query[i];
    SqrtDecomposition decomp(600001);
    bool nomore = false;
    REP(i,N) {
      int x = query[i];
      if(x >= 600000) {
        cout << "Yes" << endl;
        decomp.set1(600000);
      }
      else {
        int s = decomp.search(x);
        // DEBUG(x);
        // DEBUG(s);
        // DEBUG(decomp.check0(x + 1));
        // decomp.dump();
        if(nomore) {
          cout << "No" << endl;
        }
        else if(s == -1) {
          cout << "No" << endl;
        }
        else if(s == 0 && decomp.check0(x + 1) == false) {
          cout << "No" << endl;
        }
        else {
          decomp.set1(s);
          decomp.set0range(s + 1, x + 1);
          cout << "Yes" << endl;
          if(s == 0) nomore = true;
        }
      }
    }
  }
}