Submission #144691

#	Time	Username	Problem	Language	Result	Execution time	Memory
144691		Milki	Ili (COI17_ili)	C++14	100 / 100	1766 ms	988 KiB

ili

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 2e4 + 5;

int n, m, lt[MAXN], rt[MAXN], val[MAXN], tmp_val[MAXN];
string s;

bool go(){
  REP(i, n + m)
    tmp_val[i] = val[i];

  for(int i = n + m - 1; i >= n; --i)
    if(tmp_val[i] == 0){
      if(tmp_val[ lt[i] ] == 1) return false;
      if(tmp_val[ rt[i] ] == 1) return false;
      tmp_val[ lt[i] ] = tmp_val[ rt[i] ] = 0;
    }

  REP(i, n){
    if(tmp_val[i] == -1)
      tmp_val[i] = 1;
  }

  FOR(i, n, n + m){
    if(tmp_val[i] == -1){
      if(tmp_val[lt[i]] == 0 && tmp_val[rt[i]] == 0)
        tmp_val[i] = 0;
      else
        tmp_val[i] = 1;
    }
    else if(tmp_val[i] == 1 && tmp_val[lt[i]] == 0 && tmp_val[rt[i]] == 0)
      return false;
  }

  return true;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  memset(val, -1, sizeof(val));

  cin >> n >> m;
  cin >> s;
  REP(i, m){
    char c1, c2;
    int a, b;
    cin >> c1 >> a >> c2 >> b;
    a --; b --;

    if(c1 == 'x')
      lt[i + n] = a;
    else
      lt[i + n] = a + n;

    if(c2 == 'x')
      rt[i + n] = b;
    else
      rt[i + n] = b + n;
  }

  FOR(i, n, n + m)
    if(s[i - n] != '?')
      val[i] = s[i - n] - '0';

  FOR(i, n, n + m){
    if(val[i] != -1){
      cout << char('0' + val[i]);
      continue;
    }

    val[i] = 1;
    bool ret1 = go();
    val[i] = 0;
    bool ret2 = go();

    if(ret1 && ret2){
      val[i] = -1;
      cout << '?';
    }
    else{
      val[i] = ret1;
      cout << char('0' + ret1);
    }
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51