Submission #433027
Source Code Expand
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>
using namespace std; using namespace placeholders;
using LL = long long;
using ULL = unsigned long long;
using VI = vector< int >;
using VVI = vector< vector< int > >;
using VS = vector< string >;
using SS = stringstream;
using PII = pair< int, int >;
using VPII = vector< pair< int, int > >;
template < typename T = int > using VT = vector< T >;
template < typename T = int > using VVT = vector< vector< T > >;
template < typename T = int > using LIM = numeric_limits< T >;
template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + ( p ), ( c ).end()
#define SZ( v ) ( (int)( v ).size() )
#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter
#define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() )
#define MP make_pair
#define fst first
#define snd second
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
constexpr int INF = LIM<>::max();
VVI b( 2, VI( 3 ) ), c( 3, VI( 2 ) );
int eval( const VS &board )
{
int res = 0;
REP( i, 3 )
{
REP( j, 3 )
{
if ( i < 2 && board[i][j] == board[ i + 1 ][j] )
{
res += b[i][j];
}
if ( j < 2 && board[i][j] == board[i][ j + 1 ] )
{
res += c[i][j];
}
}
}
return res;
}
int minimax( VS &board, const int turn = 0 )
{
if ( turn == 9 )
{
return eval( board );
}
if ( turn % 2 == 0 )
{
int res = -INF;
REP( i, 3 )
{
REP( j, 3 )
{
if ( board[i][j] != '.' )
{
continue;
}
board[i][j] = 'o';
res = max( res, minimax( board, turn + 1 ) );
board[i][j] = '.';
}
}
return res;
}
else
{
int res = INF;
REP( i, 3 )
{
REP( j, 3 )
{
if ( board[i][j] != '.' )
{
continue;
}
board[i][j] = 'x';
res = min( res, minimax( board, turn + 1 ) );
board[i][j] = '.';
}
}
return res;
}
}
int main()
{
cin.tie( 0 );
ios::sync_with_stdio( false );
cin >> b >> c;
int total = 0;
for_each( ALL( b ), [&]( const VI &row ){ total += accumulate( ALL( row ), 0 ); } );
for_each( ALL( c ), [&]( const VI &row ){ total += accumulate( ALL( row ), 0 ); } );
VS init( 3, "..." );
const int res = minimax( init );
cout << res << endl << total - res << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 双子と○×ゲーム |
User |
torus711 |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
3625 Byte |
Status |
AC |
Exec Time |
98 ms |
Memory |
1048 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt |
All |
test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
sample-01.txt |
AC |
97 ms |
1040 KB |
sample-02.txt |
AC |
94 ms |
1048 KB |
test-01.txt |
AC |
98 ms |
964 KB |
test-02.txt |
AC |
94 ms |
948 KB |
test-03.txt |
AC |
95 ms |
1044 KB |
test-04.txt |
AC |
98 ms |
1044 KB |
test-05.txt |
AC |
95 ms |
952 KB |
test-06.txt |
AC |
97 ms |
948 KB |
test-07.txt |
AC |
96 ms |
952 KB |
test-08.txt |
AC |
96 ms |
1048 KB |
test-09.txt |
AC |
94 ms |
1044 KB |
test-10.txt |
AC |
93 ms |
1040 KB |
test-11.txt |
AC |
96 ms |
1040 KB |
test-12.txt |
AC |
95 ms |
1040 KB |
test-13.txt |
AC |
95 ms |
1048 KB |
test-14.txt |
AC |
96 ms |
948 KB |
test-15.txt |
AC |
95 ms |
1048 KB |
test-16.txt |
AC |
95 ms |
944 KB |
test-17.txt |
AC |
96 ms |
952 KB |
test-18.txt |
AC |
94 ms |
1048 KB |
test-19.txt |
AC |
97 ms |
1044 KB |
test-20.txt |
AC |
98 ms |
956 KB |