QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#443627 | #8789. Spin & Rotate! | zhangmj2008 | WA | 31ms | 3872kb | C++17 | 2.0kb | 2024-06-15 16:07:51 | 2024-06-15 16:07:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int; using i64 = long long; using ui64 = unsigned long long; using i128 = __int128;
const int INF = 1e9; const i64 LLNF = 4e18;
template< class Tp > void chkmax( Tp &x, Tp y ) { x = max( x, y ); }
template< class Tp > void chkmin( Tp &x, Tp y ) { x = min( x, y ); }
int log( int x ) { return 31 - __builtin_clz( x ); }
int log( i64 x ) { return 63 - __builtin_clzll( x ); }
void solve( ) {
// 神奇的论文题. [ Conway's Rational Tangles ].
// 把当前的盘面转换成数 x. 则将 Rotate 看成 r( x ) = x + 1; Spin 看成 s( x ) = - 1 / x. 初始盘面为 0.
// 那么 (1). inv S = S; (2). inv R = SRSRS. 所以现在可以将其变成初始盘面.
// 但怎么保证最简呢? 首先有几个可以删除的操作: SS = I = SRSRSR. 且最后的 RS 可以变成 S; 最后的 RSR 可以变成 I.
// 这够吗? 事实上够了.
auto emp = [&] ( string &p, char c ) -> void {
p += c;
if( ( int ) p.size( ) >= 2 && p.substr( ( int ) p.size( ) - 2 ) == "SS" ) p.pop_back( ), p.pop_back( );
if( ( int ) p.size( ) >= 6 && p.substr( ( int ) p.size( ) - 6 ) == "SRSRSR" ) p.pop_back( ), p.pop_back( ), p.pop_back( ), p.pop_back( ), p.pop_back( ), p.pop_back( );
} ;
auto simplify = [&] ( string &p ) -> void {
while( true ) {
if( ( int ) p.size( ) >= 2 && p.substr( ( int ) p.size( ) - 2 ) == "RS" ) p.pop_back( ), p.pop_back( ), emp( p, 'S' );
else if( ( int ) p.size( ) >= 3 && p.substr( ( int ) p.size( ) - 3 ) == "RSR" ) p.pop_back( ), p.pop_back( ), p.pop_back( );
else break;
}
} ;
string p; cin >> p;
string q; reverse( p.begin( ), p.end( ) );
for( char c : p ) {
if( c == 'R' ) emp( q, 'S' ), emp( q, 'R' ), emp( q, 'S' ), emp( q, 'R' ), emp( q, 'S' );
else if( c == 'S' ) emp( q, 'S' );
else assert( 0 );
}
simplify( q );
cout << ( q.empty( ) ? "S" : q ) << "\n";
}
int main( ) {
ios::sync_with_stdio( 0 ), cin.tie( 0 ), cout.tie( 0 );
int T; cin >> T; while( T -- ) solve( ); return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
input:
14 R S RR SR RS SS RRR SRR RSR SSR RRS SRS RSS SSS
output:
SR S SRSRR S R S SRSRRSRR S S SR RSRR S SR S
result:
ok 14 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
5 SRRSRRSRR SRRRSRRR RRRSRRRSRRR SRRSRRSRRSRRSRRSRRSRRSRRSRRSR SRRRSRRRSRRRSRRRSRRRSRRRSRRRS
output:
SRSRRR SRSRRSRR SRSRRSRRRSRRRSRR SRRRRRRRRR RSRRSRRRSRRRSRRRSRRRSRRRSRR
result:
ok 5 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
16 RRRR SRRR RSRR SSRR RRSR SRSR RSSR SSSR RRRS SRRS RSRS SSRS RRSS SRSS RSSS SSSS
output:
SRSRRSRRSRR S SR SRSRR SRR SR SRSRR S RSRRSRR S S R SRSRR S R S
result:
ok 16 tokens
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
32 RRRRR SRRRR RSRRR SSRRR RRSRR SRSRR RSSRR SSSRR RRRSR SRRSR RSRSR SSRSR RRSSR SRSSR RSSSR SSSSR RRRRS SRRRS RSRRS SSRRS RRSRS SRSRS RSSRS SSSRS RRRSS SRRSS RSRSS SSRSS RRSSS SRSSS RSSSS SSSSS
output:
SRSRRSRRSRRSRR S SRSRR SRSRRSRR SRSRRR SRSRR SRSRRSRR S SRRSRR SR S S SRSRRSRR S S SR RSRRSRRSRR S R RSRR RR R RSRR S SRSRRSRR S S SR RSRR S SR S
result:
ok 32 tokens
Test #5:
score: 0
Accepted
time: 17ms
memory: 3632kb
input:
300000 S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S...
output:
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S ...
result:
ok 300000 tokens
Test #6:
score: 0
Accepted
time: 30ms
memory: 3800kb
input:
300000 R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R...
output:
SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR ...
result:
ok 300000 tokens
Test #7:
score: 0
Accepted
time: 31ms
memory: 3856kb
input:
150000 RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR RR...
output:
SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR SRSRR ...
result:
ok 150000 tokens
Test #8:
score: 0
Accepted
time: 29ms
memory: 3872kb
input:
100000 RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR RRR R...
output:
SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRSRRSRR SRS...
result:
ok 100000 tokens
Test #9:
score: -100
Wrong Answer
time: 18ms
memory: 3572kb
input:
23723 RRRRRR SRRRRR RSRRRR SSRRRR RRSRRR SRSRRR RSSRRR SSSRRR RRRSRR SRRSRR RSRSRR SSRSRR RRSSRR SRSSRR RSSSRR SSSSRR RRRRSR SRRRSR RSRRSR SSRRSR RRSRSR SRSRSR RSSRSR SSSRSR RRRSSR SRRSSR RSRSSR SSRSSR RRSSSR SRSSSR RSSSSR SSSSSR RRRRRS SRRRRS RSRRRS SSRRRS RRSRRS SRSRRS RSSRRS SSSRRS RRRSRS SRRSRS ...
output:
SRSRRSRRSRRSRRSRR S SRSRRSRR SRSRRSRRSRR SRSRRSRRR SRSRRSRR SRSRRSRRSRR S SRSRRRSRR SRSRR S SR SRSRRSRRSRR S SR SRSRR SRRSRRSRR SR S SRR R S SRR SR SRSRRSRRSRR S SR SRSRR SRR SR SRSRR S RSRRSRRSRRSRR S RSRR RSRRSRR RSRRR RSRR RSRRSRR S RRSRR R S S RSRRSRR S S R SRSRRSRRSRR S SR SRSRR SRR SR SRSRR S ...
result:
wrong answer 85th words differ - expected: 'S', found: 'SRSRRSRSRR'