oj.uz

Submission #12114

# Submission time Handle Problem Language Result Execution time Memory
12114 2014-12-21T07:23:19 Z ainu7 전선 연결하기 (GA9_wire) C++
24 / 100
 1000 ms 5100 KB 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

char res[600002];
int area[600002];

bool solve(int ll, int rr, vector<int>& A, vector<int>& other) {
  if (ll > rr) return true;
  res[ll] = '^';
  res[other[ll]] = '^';

  while (1) {
    area[ll] = 0;
    for (int i=ll+1; i<=rr; i++)
      area[i] = area[i-1] + (res[i] == '^' || res[i] == 'v');
    int ok = 0;
    for (int i=ll+1; i<=rr; i++)
      if (res[i] != '^' && res[i] != 'v' && area[i] != area[other[i]]) {
        int lll = i;
        int rrr = other[i];
        if (lll > rrr) swap(lll, rrr);
        int p1 = 0, p2 = 0;
        for (int j=lll+1; j<=rrr-1; j++)
          if (res[j] == '^' && (other[j] < lll || other[j] > rrr)) p1 = 1;
          else if (res[j] == 'v' && (other[j] < lll || other[j] > rrr)) p2 = 1;
        if (p1 && p2) return false;
        if (p1) res[lll] = res[rrr] = 'v';
        else res[lll] = res[rrr] = '^';
        ok = 1;
        break;
      }
    if (!ok) break;
  }

  int st = ll+1;
  for (int i=ll+1; i<=rr; i++)
    if (res[i] == '^' || res[i] == 'v') {
      bool ret = solve(st, i-1, A, other);
      if (!ret) return false;
      st = i+1;
    }
  return solve(st, rr, A, other);
}

int main()
{
  int n;
  cin >> n;
  vector<int> A(2*n);
  vector<pair<int, int> > P;
  for (int i=0; i<2*n; i++) {
    cin >> A[i];
    A[i] --;
    P.push_back(pair<int, int>(A[i], i));
  }
  sort(P.begin(), P.end());
  vector<int> other(2*n);
  for (int i=0; i<2*n; i+=2) {
    int a = P[i].second;
    int b = P[i+1].second;
    other[a] = b;
    other[b] = a;
  }

  for (int i=0; i<2*n; i++) res[i] = '_';
  res[2*n] = 0;

  bool ret = solve(0, 2*n-1, A, other);

  if (ret) cout << res << endl;
  else cout << "IMPOSSIBLE" << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4608 KB Output is correct
2 Correct 0 ms 4608 KB Output is correct
3 Correct 0 ms 4608 KB Output is correct
4 Correct 0 ms 4608 KB Output is correct
5 Correct 0 ms 4608 KB Output is correct
6 Correct 0 ms 4608 KB Output is correct
7 Correct 0 ms 4608 KB Output is correct
8 Correct 0 ms 4608 KB Output is correct
9 Correct 0 ms 4608 KB Output is correct
10 Correct 0 ms 4608 KB Output is correct
11 Correct 0 ms 4608 KB Output is correct
12 Correct 0 ms 4608 KB Output is correct
13 Correct 0 ms 4608 KB Output is correct
14 Correct 0 ms 4608 KB Output is correct
15 Correct 0 ms 4608 KB Output is correct
16 Correct 0 ms 4608 KB Output is correct
17 Correct 0 ms 4608 KB Output is correct
18 Correct 0 ms 4608 KB Output is correct
19 Correct 0 ms 4608 KB Output is correct
20 Correct 0 ms 4608 KB Output is correct
21 Correct 0 ms 4608 KB Output is correct
22 Correct 0 ms 4608 KB Output is correct
23 Correct 0 ms 4608 KB Output is correct
24 Correct 0 ms 4608 KB Output is correct
25 Correct 0 ms 4608 KB Output is correct
26 Correct 0 ms 4608 KB Output is correct
27 Correct 0 ms 4608 KB Output is correct
28 Correct 0 ms 4608 KB Output is correct
29 Correct 0 ms 4608 KB Output is correct
30 Correct 0 ms 4608 KB Output is correct
31 Correct 0 ms 4608 KB Output is correct
32 Correct 0 ms 4608 KB Output is correct
33 Correct 0 ms 4608 KB Output is correct
34 Correct 0 ms 4608 KB Output is correct
35 Correct 0 ms 4608 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4608 KB Output is correct
2 Correct 0 ms 4608 KB Output is correct
3 Correct 0 ms 4608 KB Output is correct
4 Correct 0 ms 4608 KB Output is correct
5 Correct 0 ms 4608 KB Output is correct
6 Correct 4 ms 4608 KB Output is correct
7 Correct 0 ms 4608 KB Output is correct
8 Correct 4 ms 4608 KB Output is correct
9 Correct 0 ms 4608 KB Output is correct
10 Correct 0 ms 4608 KB Output is correct
11 Correct 0 ms 4608 KB Output is correct
12 Correct 4 ms 4608 KB Output is correct
13 Correct 8 ms 4608 KB Output is correct
14 Correct 4 ms 4608 KB Output is correct
15 Correct 0 ms 4608 KB Output is correct
16 Correct 4 ms 4608 KB Output is correct
17 Correct 8 ms 4608 KB Output is correct
18 Correct 4 ms 4608 KB Output is correct
19 Correct 0 ms 4608 KB Output is correct
20 Correct 0 ms 4608 KB Output is correct
21 Correct 0 ms 4608 KB Output is correct
22 Correct 8 ms 4608 KB Output is correct

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 5100 KB Output is correct
2 Execution timed out 1000 ms 5100 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -