Submission #12114

#	Time	Username	Problem	Language	Result	Execution time	Memory
12114		ainu7	전선 연결하기 (GA9_wire)	C++98	24 / 100	1000 ms	5100 KiB

wire

#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 / 9
• Subtask 2: 15 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39