#34870 (C++11(old_compat)) No.232 めぐるはめぐる (2)

• 問題: No.232 めぐるはめぐる (2)
• ユーザー: yuppe19 😺
• 提出日時: 2015-07-01 10:20:36
• 言語: C++11(old_compat) (gcc 12.4.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 35 ms / 1,000 ms
• コード長: 3,885 bytes
• コンパイル時間: 1,920 ms
• コンパイル使用メモリ: 193,412 KB
• 実行使用メモリ: 8,932 KB
• 最終ジャッジ日時: 2026-03-08 16:02:55
• 合計ジャッジ時間: 3,348 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 22

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:142:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  142 |   int t, a, b; scanf("%d%d%d", &t, &a, &b);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

const int N = 624;
const int M = 397;
const unsigned int MATRIX_A   = 0x9908b0dfU;
const unsigned int UPPER_MASK = 0x80000000U;
const unsigned int LOWER_MASK = 0x7fffffffU;

static unsigned int mt[N];
static int mti = N + 1;

void init_genrand(unsigned int s) {
  mt[0] = s & 0xffffffffU;
  for(mti=1; mti<N; mti++) {
    mt[mti] = (1812433253U * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
    mt[mti] &= 0xffffffffU;
  }
}

void init_by_array(vector<unsigned int> init_key) {
  int key_length = init_key.size();
  init_genrand(19880731U); // まいぷる
  int i = 1, j = 0;
  int k = N > key_length ? N : key_length;
  for( ; k; k--) {
    mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U)) + init_key[j] + j;
    mt[i] &= 0xffffffffU;
    i++; j++;
    if(i >= N) { mt[0] = mt[N-1]; i = 1; }
    if(j >= key_length) { j = 0; }
  }
  for(k=N-1; k; k--) {
    mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U)) - i;
    mt[i] &= 0xffffffffU;
    i++;
    if(i >= N) { mt[0] = mt[N-1]; i = 1; }
  }
  mt[0] = 0x80000000U;
}

unsigned int genrand_int32(void) {
  unsigned int y;
  static unsigned int mag01[2] = {0x0U, MATRIX_A};
  if(mti >= N) {
    if(mti == N + 1) { init_genrand(5489U); }
    int kk;
    for(kk=0; kk<N-M; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
      mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
    }
    for(; kk<N-1; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
      mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
    }
    y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
    mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
    mti = 0;
  }
  y = mt[mti++];
  y ^= (y >> 11);
  y ^= (y << 7) & 0x9d2c5680U;
  y ^= (y << 15) & 0xefc60000U;
  y ^= (y >> 18);
  return y;
}

template<class T>
T choice(vector<T> &v) {
  int n = v.size();
  return v[genrand_int32() % n];
}

class Point {
public:
  int x, y;
  Point(int _x, int _y) : x(_x), y(_y) {};
};

vector<string> solve(int t, int a, int b) {
//  if(t < max(a, b)) { return vector<string>(); }
  map<int, string> kortx, korty;
  kortx[-1] = "<";
  kortx[ 0] = "";
  kortx[ 1] = ">";
  korty[-1] = "v";
  korty[ 0] = "";
  korty[ 1] = "^";
  vector<Point> d;
  for(int x : range(-1, 2)) {
    for(int y : range(-1, 2)) {
      if(x == 0 && y == 0) { continue; }
      d.push_back(Point(x, y));
    }
  }
  int t2 = t - 4;
  int cx = 0, cy = 0;
  vector<string> res;
  for(int i : range(min(t2, max(a, b)))) {
    string s;
    if(i <= b) { s += '>'; cx++; }
    if(i <= a) { s += '^'; cy++; }
    res.push_back(s);
  }
  int left2 = t2 - res.size();
  for(int i : range(left2/2)) {
    res.push_back("<");// cx--;
    res.push_back(">");// cx++;
  }
  for(int times : range(100000)) {
    int x1 = cx, y1 = cy;
    int left = t - res.size();
    vector<string> extra;
    for(int i : range(left)) {
      Point p = choice(d);
      x1 += p.x;
      y1 += p.y;
      extra.push_back(kortx[p.x] + korty[p.y]);
    }
    if(x1 == b && y1 == a) {
      res.insert(res.end(), extra.begin(), extra.end());
      return res;
    }
  }
  return vector<string>();
}

int main(void) {
  time_t seed = time(0);
  vector<unsigned int> init;
  init.push_back(0x123);
  init.push_back(0x234);
  init.push_back(0x345);
  init.push_back(0x456);
  init.push_back(seed);
  init_by_array(init);
  int t, a, b; scanf("%d%d%d", &t, &a, &b);
  vector<string> res = solve(t, a, b);
  if(!res.size()) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for(int i : range(res.size())) {
    puts(res[i].c_str());
  }
  return 0;
}