oj.uz

Submission #119668

# Submission time Handle Problem Language Result Execution time Memory
119668 2019-06-21T16:48:42 Z Milki Alternating Current (BOI18_alternating) C++14
19 / 100
 141 ms 11648 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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Incorrect 5 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Incorrect 5 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Incorrect 5 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 11648 KB Output is correct
2 Correct 39 ms 5120 KB Output is correct
3 Correct 71 ms 8460 KB Output is correct
4 Correct 90 ms 8408 KB Output is correct
5 Correct 134 ms 10596 KB Output is correct
6 Correct 101 ms 10340 KB Output is correct
7 Correct 120 ms 9572 KB Output is correct
8 Correct 46 ms 5396 KB Output is correct
9 Correct 37 ms 5248 KB Output is correct
10 Correct 134 ms 10848 KB Output is correct
11 Correct 112 ms 9056 KB Output is correct
12 Correct 128 ms 11236 KB Output is correct
13 Correct 22 ms 5120 KB Output is correct
14 Correct 21 ms 5120 KB Output is correct
15 Correct 120 ms 10208 KB Output is correct
16 Correct 50 ms 8564 KB Output is correct
17 Correct 141 ms 9852 KB Output is correct
18 Correct 94 ms 10188 KB Output is correct
19 Correct 25 ms 5568 KB Output is correct
20 Correct 100 ms 11360 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Incorrect 5 ms 3072 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -