Submission #119921

#	Time	Username	Problem	Language	Result	Execution time	Memory
119921		Milki	Alternating Current (BOI18_alternating)	C++14	100 / 100	175 ms	18912 KiB

alternating

#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 = 2e5 + 5, off = 1 << 18;

struct event{
  int x = -1, y = -1, id = -1;
  event(){}
  event(int x, int y, int id) : x(x), y(y), id(id) {}

  friend bool operator < (const event &A, const event &B){
    if(A.x != B.x) return A.x < B.x;
    return A.y > B.y;
  }
};

int n, m, par[MAXN];
event rail[MAXN];
vector <event> v, ev;
vector <int> djeca[MAXN];
bool sol[MAXN];

struct Tournament{
  int t[2 * off], p[2 * off];

  Tournament(){}
  void reset(){
    memset(t, 0, sizeof(t));
    memset(p, -1, sizeof(p));
  }
  void prop(int x, int lo, int hi){
    if(p[x] == -1)
      return;
    t[x] = p[x] * (hi - lo);
    if(x < off){
      p[x * 2] = p[x];
      p[x * 2 + 1] = p[x];
    }
    p[x] = -1;
  }
  void update(int x, int lo, int hi, int a, int b, int val){
    prop(x, lo, hi);
    if(lo >= b || hi <= a) return;
    if(lo >= a && hi <= b) { p[x] = val; prop(x, lo, hi); return; }
    int mid = (lo + hi) >> 1;
    update(x * 2, lo, mid, a, b, val); update(x * 2 + 1, mid, hi, a, b, val);
    t[x] = t[x * 2] + t[x * 2 + 1];
  }
  int get(int x, int lo, int hi, int a, int b){
    prop(x, lo, hi);
    if(lo >= b || hi <= a) return 0;
    if(lo >= a && hi <= b) return t[x];
    int mid = (lo + hi) >> 1;
    return get(x * 2, lo, mid, a, b) +
           get(x * 2 + 1, mid, hi, a, b);
  }

} T;

bool check(int x){
  T.reset();
  REP(i, m){
    if(sol[i] == x){
      if(rail[i].x > rail[i].y){
        T.update(1, 0, off, rail[i].x, n + 1, 1);
        T.update(1, 0, off, 1, rail[i].y + 1, 1);
      }
      else{
        T.update(1, 0, off, rail[i].x, rail[i].y + 1, 1);
      }
    }
  }

  if(T.get(1, 0, off, 1, n + 1) == n)
    return true;
  else
    return false;
}

void ubaci(int x, int y){
  if(x > y){
    T.update(1, 0, off, x, n + 1, 1);
    T.update(1, 0, off, 1, y + 1, 1);
  }
  else{
    T.update(1, 0, off, x, y + 1, 1);
  }
}

void izbaci(int x, int y){
  if(x > y){
    T.update(1, 0, off, x, n + 1, 0);
    T.update(1, 0, off, 1, y + 1, 0);
  }
  else{
    T.update(1, 0, off, x, y + 1, 0);
  }
}

bool provjeri(event A){
  if(A.x > A.y){
    if(T.get(1, 0, off, A.x, n + 1) != n - A.x + 1)
      return false;
    if(T.get(1, 0, off, 1, A.y + 1) != A.y)
      return false;
  }
  else{
    if(T.get(1, 0, off, A.x, A.y + 1) != A.y - A.x + 1)
      return false;
  }
  return true;
}

bool moze(event A, event B, event C, event D){
  // A i B moraju bit pokriveni sa C i D
  ubaci(C.x, C.y); ubaci(D.x, D.y);

  for(auto it : djeca[A.id])
    ubaci(rail[it].x, rail[it].y);
  for(auto it : djeca[B.id])
    ubaci(rail[it].x, rail[it].y);

  bool ret;
  if(provjeri(A) && provjeri(B))
    ret = true;
  else
    ret = false;

  izbaci(C.x, C.y); izbaci(D.x, D.y);
  for(auto it : djeca[A.id])
    izbaci(rail[it].x, rail[it].y);
  for(auto it : djeca[B.id])
    izbaci(rail[it].x, rail[it].y);
  return ret;
}

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

  cin >> n >> m;
  REP(i, m){
    int a, b; cin >> a >> b;
    rail[i] = event(a, b, i);

    if(a <= b)
      v.pb(event(a, b, i));
    if(a > b)
      v.pb(event(a, b + n, i));
    else
      v.pb(event(a + n, b + n, i));
  }
  sort(v.begin(), v.end());

  event curr = v[0];
  FOR(i, 1, sz(v)){
    if(curr.x <= v[i].x && curr.y >= v[i].y){
      par[ v[i].id ] = curr.id;
    }

    if(curr.y < v[i].y)
      curr = v[i];
  }

  REP(i, m)
    if(par[i] == i || par[i] == -1)
      ev.pb(rail[i]);
  sort(ev.begin(), ev.end());
  T.reset();

  for(int i = 0; i < sz(ev); i += 2)
    sol[ ev[i].id ] = true;
  REP(i, m){
    if(par[i] != i && par[i] != -1){
      djeca[ par[i] ].pb(i);
      sol[i] = !sol[ par[i] ] ;
    }
  }
  if(sz(ev) % 2 == 0){
    if(check(0) && check(1))
      REP(i, m)
        cout << sol[i];
    else{
      cout << "impossible";
    }
  }
  else{
    REP(i, m)
      sol[i] = 0;

    REP(i, sz(ev)){
      if(moze( ev[(i + 1) % sz(ev)], ev[(i + 2) % sz(ev)], ev[(i) % sz(ev)], ev[(i + 3) % sz(ev)] )){

        for(int j = (i + 1) % sz(ev); j >= 0; j -= 2)
          sol[ ev[j].id ] = 1;
        for(int j = (i + 2) % sz(ev); j < sz(ev); j += 2)
          sol[ ev[j].id ] = 1;

        REP(j, m)
          if(par[j] != j && par[j] != -1)
            sol[j] = !sol[par[j]];

        if(check(0) && check(1))
          REP(j, m)
            cout << sol[j];
        else
          cout << "impossible";
        return 0;
      }
    }
    cout << "impossible";
  }
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26