oj.uz

Submission #119654

# Submission time Handle Problem Language Result Execution time Memory
119654 2019-06-21T15:35:01 Z Milki Alternating Current (BOI18_alternating) C++14
19 / 100
 137 ms 8876 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;
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 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());

  for(int i = 0; i < sz(ev); i += 2)
    sol[ ev[i].id ] = true;
  REP(i, m){
    if(par[i] != i && par[i] != -1)
      sol[i] = !sol[ par[i] ];
  }

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Incorrect 4 ms 2816 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 5 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Incorrect 4 ms 2816 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 5 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Incorrect 4 ms 2816 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 118 ms 7576 KB Output is correct
2 Correct 37 ms 2832 KB Output is correct
3 Correct 56 ms 5352 KB Output is correct
4 Correct 70 ms 5364 KB Output is correct
5 Correct 128 ms 8648 KB Output is correct
6 Correct 129 ms 8332 KB Output is correct
7 Correct 118 ms 7500 KB Output is correct
8 Correct 40 ms 3028 KB Output is correct
9 Correct 37 ms 2936 KB Output is correct
10 Correct 131 ms 8876 KB Output is correct
11 Correct 99 ms 7016 KB Output is correct
12 Correct 107 ms 7272 KB Output is correct
13 Correct 21 ms 2816 KB Output is correct
14 Correct 20 ms 2816 KB Output is correct
15 Correct 115 ms 7780 KB Output is correct
16 Correct 50 ms 6636 KB Output is correct
17 Correct 137 ms 7856 KB Output is correct
18 Correct 89 ms 7648 KB Output is correct
19 Correct 23 ms 3264 KB Output is correct
20 Correct 91 ms 7904 KB Output is correct

Subtask #5
0 / 26.0

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