QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #363105 | #6568. Space Alignment | distant_yesterday# | AC ✓ | 1ms | 3800kb | C++14 | 3.8kb | 2024-03-23 18:22:39 | 2024-03-23 18:22:40 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug(...) 42
// #include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
template<typename T> void write(T x) {
if(x > 9) write(x/10);
putchar(x%10 + '0');
}
void solve() {
int n;
read(n);
vi dep(n, -1), ns(n, 0), nt(n, 0);
int cdep = 0;
rep(i,0,n) {
string s;
cin >> s;
char end = s.back();
if(end == '{') {
dep[i] = cdep;
cdep++;
} else {
assert(end == '}');
cdep--;
dep[i] = cdep;
}
assert(cdep >= 0);
s.pop_back();
for(auto c: s) {
if(c == 's') {
ns[i]++;
} else if(c == 't') {
nt[i]++;
} else {
assert(false);
}
}
}
assert(ns[0] == 0 && nt[0] == 0 && dep[0] == 0);
assert(ns[n-1] == 0 && nt[n-1] == 0 && dep[n-1] == 0);
if(n == 2) {
cout<<1<<'\n';
return;
}
int base_s = -1, base_t = -1, ans = -1;
rep(i,0,n) if(dep[i]==1) {
base_s = ns[i];
base_t = nt[i];
break;
}
if(base_s == -1 || base_t == -1) {
assert(base_s == -1 && base_t == -1);
rep(i,0,n) {
assert(dep[i] == 0);
if(ns[i] > 0 || nt[i] > 0) {
cout<<-1<<'\n';
return;
}
}
cout<<1<<'\n';
return;
}
debug(dep, ns, nt, base_s, base_t);
if(base_s == 0 && base_t == 0) {
cout<<-1<<'\n';
return;
}
rep(i, 0, n) {
if(dep[i] == 0) {
if(ns[i] > 0 || nt[i] > 0) {
cout<<-1<<'\n';
return;
}
} else {
assert(dep[i] > 0);
if(base_t * dep[i] == nt[i]) {
if(ns[i] != base_s*dep[i]) {
cout<<-1<<'\n';
return;
}
debug("colinear");
} else {
// ns[i]+nt[i]*ans==base_s*dep+base_t*dep*ans
// ans = (base_s*dep-ns[i]) / (nt[i]-base_t*dep)
debug(ns[i],nt[i],base_s,base_t,dep[i]);
int de = nt[i]-base_t*dep[i];
int nu = base_s*dep[i]-ns[i];
if(de < 0) {
nu *= -1, de *= -1;
if(nu <= 0) {
cout<<-1<<'\n';
return;
}
}
debug(nu, de, ans);
if(nu % de != 0) {
cout<<-1<<'\n';
return;
}
int new_ans = nu / de;
assert(new_ans > 0);
if(ans == -1) {
ans = new_ans;
} else {
if(ans != new_ans) {
cout<<-1<<'\n';
return;
}
}
}
}
}
if(ans == -1) ans = 1;
cout << ans << '\n';
}
// akt+kb==ct+d
signed main() {
int T; T=1;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3524kb
input:
10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2
{
}
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
4
{
ss{
ss}
}
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
4
{
tt{
tt}
}
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
4
{
ss{
s}
}
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
4
{
tt{
t}
}
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
4
{
tt{
s}
}
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
4
{
tt{
sss}
}
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
4
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
6
{
}
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
100
{
}
{
}
{
t{
ssssssssssssssssssssssssssssssssssss}
t{
t}
t{
tssssssssssssssssssssssssssssssssssss{
tssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss{
tsssssssssssssssssssssssssssssssssssst}
ttssssssssssssssssssssssssssssssssssss{
ssssssssssssssssssssssssssssssssssssssssss...
output:
36
result:
ok single line: '36'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'