Submission #1049149


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

int main() {
  string tmp;
  cin >> tmp;
  int n = tmp.length();
  vector<string> s(n);
  rep (i, n) {
    s[i] = tmp.substr(i, n-i) + tmp.substr(0, i);
  }
  deque<deque<bool> > pattern(n, deque<bool>(n));
  rep (i, n) {
    rep(j, n) {
      pattern[i][j] = (s[i][j] == 'o') ? true : false;
    }
  }

  int ans = 20;
  int m = (1 << n);
  FOR (i, 1, m) {
    int cnt = 0;
    deque<bool> possible(n, false);
    rep (j, n) {
      if ((i >> j) % 2 == 0) {
        continue;
      }
      cnt += 1;
      rep (k, n) {
        possible[k] |= pattern[j][k];
      }
    }
    bool flag = true;
    rep (j, n) {
      flag &= possible[j];
    }
    if (flag) {
      ans = min(ans, cnt);
    }
  }
  printf("%d\n", ans);

  return 0;
}

Submission Info

Submission Time
Task C - 節約生活
User tspcx
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1673 Byte
Status AC
Exec Time 21 ms
Memory 1052 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 53
Set Name Test Cases
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rand_00.txt, 01_rand_01.txt, 01_rand_02.txt, 01_rand_03.txt, 01_rand_04.txt, 01_rand_05.txt, 01_rand_06.txt, 01_rand_07.txt, 01_rand_08.txt, 01_rand_09.txt, 01_rand_10.txt, 01_rand_11.txt, 01_rand_12.txt, 01_rand_13.txt, 01_rand_14.txt, 01_rand_15.txt, 01_rand_16.txt, 01_rand_17.txt, 01_rand_18.txt, 01_rand_19.txt, 02_maxrand_00.txt, 02_maxrand_01.txt, 02_maxrand_02.txt, 02_maxrand_03.txt, 02_maxrand_04.txt, 02_maxrand_05.txt, 02_maxrand_06.txt, 02_maxrand_07.txt, 02_maxrand_08.txt, 02_maxrand_09.txt, 02_maxrand_10.txt, 02_maxrand_11.txt, 02_maxrand_12.txt, 02_maxrand_13.txt, 02_maxrand_14.txt, 02_maxrand_15.txt, 02_maxrand_16.txt, 02_maxrand_17.txt, 02_maxrand_18.txt, 02_maxrand_19.txt, 03_max.txt, 03_maxret.txt, 03_min.txt, 03_special_01.txt, 03_special_02.txt, 03_special_03.txt, 03_special_04.txt, 04_special_05.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 21 ms 1048 KB
00_sample_02.txt AC 18 ms 928 KB
00_sample_03.txt AC 20 ms 1052 KB
00_sample_04.txt AC 20 ms 1052 KB
00_sample_05.txt AC 18 ms 928 KB
01_rand_00.txt AC 20 ms 924 KB
01_rand_01.txt AC 20 ms 1044 KB
01_rand_02.txt AC 18 ms 1052 KB
01_rand_03.txt AC 19 ms 1048 KB
01_rand_04.txt AC 20 ms 924 KB
01_rand_05.txt AC 19 ms 940 KB
01_rand_06.txt AC 20 ms 916 KB
01_rand_07.txt AC 21 ms 920 KB
01_rand_08.txt AC 20 ms 928 KB
01_rand_09.txt AC 20 ms 912 KB
01_rand_10.txt AC 19 ms 916 KB
01_rand_11.txt AC 20 ms 1052 KB
01_rand_12.txt AC 19 ms 928 KB
01_rand_13.txt AC 20 ms 1048 KB
01_rand_14.txt AC 19 ms 952 KB
01_rand_15.txt AC 20 ms 920 KB
01_rand_16.txt AC 21 ms 924 KB
01_rand_17.txt AC 19 ms 972 KB
01_rand_18.txt AC 20 ms 916 KB
01_rand_19.txt AC 21 ms 920 KB
02_maxrand_00.txt AC 20 ms 1052 KB
02_maxrand_01.txt AC 20 ms 1052 KB
02_maxrand_02.txt AC 20 ms 1052 KB
02_maxrand_03.txt AC 21 ms 928 KB
02_maxrand_04.txt AC 21 ms 1048 KB
02_maxrand_05.txt AC 21 ms 1048 KB
02_maxrand_06.txt AC 19 ms 1044 KB
02_maxrand_07.txt AC 20 ms 1044 KB
02_maxrand_08.txt AC 21 ms 920 KB
02_maxrand_09.txt AC 20 ms 1052 KB
02_maxrand_10.txt AC 21 ms 920 KB
02_maxrand_11.txt AC 20 ms 928 KB
02_maxrand_12.txt AC 21 ms 1048 KB
02_maxrand_13.txt AC 21 ms 1052 KB
02_maxrand_14.txt AC 21 ms 1052 KB
02_maxrand_15.txt AC 20 ms 1052 KB
02_maxrand_16.txt AC 21 ms 1048 KB
02_maxrand_17.txt AC 21 ms 1048 KB
02_maxrand_18.txt AC 21 ms 1052 KB
02_maxrand_19.txt AC 21 ms 928 KB
03_max.txt AC 21 ms 1048 KB
03_maxret.txt AC 18 ms 1052 KB
03_min.txt AC 19 ms 1048 KB
03_special_01.txt AC 20 ms 1040 KB
03_special_02.txt AC 19 ms 1044 KB
03_special_03.txt AC 19 ms 928 KB
03_special_04.txt AC 21 ms 1040 KB
04_special_05.txt AC 20 ms 1036 KB