oj.uz

답안 #119667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119667 2019-06-21T16:47:40 Z Milki Alternating Current (BOI18_alternating) C++14
19 / 100
 209 ms 11716 KB 
#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 = 1e5 + 5, off = 1 << 17;

struct event{
  int x, y, id;
  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, 0, sizeof(p));
  }
  void prop(int x){
    if(!t[x])
      t[x] = p[x];
    if(x < off){
      p[x * 2] = max(p[x], p[x * 2]);
      p[x * 2 + 1] = max(p[x], p[x * 2 + 1]);
    }
    p[x] = 0;
  }
  void update(int x, int lo, int hi, int a, int b){
    prop(x);
    if(lo >= b || hi <= a) return;
    if(lo >= a && hi <= b) { p[x] = 1; prop(x); return; }
    int mid = (lo + hi) >> 1;
    update(x * 2, lo, mid, a, b); update(x * 2 + 1, mid, hi, a, b);
  }
  int get(int x, int lo, int hi, int a, int b){
    prop(x);
    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);
        T.update(1, 0, off, 1, rail[i].y + 1);
      }
      else{
        T.update(1, 0, off, rail[i].x, rail[i].y + 1);
      }
    }
  }
  int sum = 0;
  REP(i, n)
    sum += T.get(1, 0, off, i + 1, i + 2);

  if(sum == n)
    return true;
  else
    return false;
}

int parent[MAXN];

int f(int x){
  if(parent[x] == x) return x;
  return par[x] = f(par[x]);
}

void spoji(int x, int y){
  x = f(x); y = f(y);
  if(x == y) return;
  parent[y] = x;
}

bool moze(event A, event B, event C, event D){
  // A i B moraju bit pokriveni sa C i D
  if(A.x > A.y) A.y += n;
  if(B.x > B.y) B.y += n;
  if(C.x > C.y) C.y += n;
  if(D.x > D.y) D.y += n;
  /*TRACE(A.id); TRACE(B.id); TRACE(C.id); TRACE(D.id);
  for(auto e : djeca[A.id])
    TRACE(e);
  for(auto e : djeca[B.id])
    TRACE(e); */
  vector <point> tmp;
  tmp.pb(point(C.x, C.y));
  tmp.pb(point(D.x, D.y));
  for(auto it : djeca[A.id])
    tmp.pb(point(rail[it].x, rail[it].y)) ;
  for(auto it : djeca[B.id])
    tmp.pb(point(rail[it].x, rail[it].y));
  REP(i, sz(tmp))
    if(tmp[i].first > tmp[i].second)
      tmp[i].second += n;
  sort(tmp.begin(), tmp.end());
  int l = tmp[0].first, r = tmp[0].second;
  for(auto it : tmp){
    if(r + 1 < it.first){
      return false;
    }
    r = max(r, it.second);
  }

  if(r >= B.y)
    return true;
  else
    return false;
}

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);
    parent[i] = 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;
      spoji(curr.id, v[i].id);
    }

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

  REP(i, m)
    if(f(i) == i)
      ev.pb(rail[i]);
  sort(ev.begin(), ev.end());
  //REP(i, m)
   // cout << parent[i] << " ";
  //cout <<"\n";
  for(int i = 0; i < sz(ev); i += 2)
    sol[ ev[i].id ] = true;
  REP(i, m){
    if(f(i) != i){
      djeca[ f(i) ].pb(i);
      sol[i] = !sol[ f(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(f(j) != j)
            sol[j] = !sol[f(j)];

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

Compilation message

alternating.cpp: In function 'bool moze(event, event, event, event)':
alternating.cpp:126:7: warning: unused variable 'l' [-Wunused-variable]
   int l = tmp[0].first, r = tmp[0].second;
       ^

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Incorrect 4 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Incorrect 4 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Incorrect 4 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 11716 KB Output is correct
2 Correct 38 ms 5120 KB Output is correct
3 Correct 69 ms 8412 KB Output is correct
4 Correct 89 ms 8464 KB Output is correct
5 Correct 134 ms 10560 KB Output is correct
6 Correct 152 ms 10292 KB Output is correct
7 Correct 209 ms 9616 KB Output is correct
8 Correct 42 ms 5376 KB Output is correct
9 Correct 38 ms 5220 KB Output is correct
10 Correct 159 ms 10848 KB Output is correct
11 Correct 117 ms 9056 KB Output is correct
12 Correct 134 ms 11244 KB Output is correct
13 Correct 22 ms 5120 KB Output is correct
14 Correct 27 ms 5120 KB Output is correct
15 Correct 125 ms 10292 KB Output is correct
16 Correct 100 ms 8556 KB Output is correct
17 Correct 149 ms 9812 KB Output is correct
18 Correct 103 ms 10104 KB Output is correct
19 Correct 26 ms 5568 KB Output is correct
20 Correct 111 ms 11360 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Incorrect 4 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -