QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#443627#8789. Spin & Rotate!zhangmj2008WA 31ms3872kbC++172.0kb2024-06-15 16:07:512024-06-15 16:07:52

Judging History

This is the latest submission verdict.

  • [2024-06-15 16:07:52]
  • Judged
  • Verdict: WA
  • Time: 31ms
  • Memory: 3872kb
  • [2024-06-15 16:07:51]
  • Submitted

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'