QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #354799 | #6568. Space Alignment | kevinshan# | WA | 1ms | 3872kb | C++17 | 4.4kb | 2024-03-16 01:58:11 | 2024-03-16 01:58:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define iii array<int, 3>
const int oo = 1e9;
stack<iii> st;
string s[1010];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
}
int n; cin>>n;
int iden = -1, dif = -oo;
int difv = -oo, difc = -oo;
for (int i=1; i<=n; i++)
{
// cout<<"AT: "<<i<<" "<<iden<<" "<<dif<<"\n";
cin>>s[i];
int v = 0, c = 0;
for (char cc: s[i])
{
if (cc == 't') v++;
else if (cc == 's') c++;
else
{
// cout<<"HUH: "<<v<<" "<<c<<"\n";
if (cc == '{')
{
if (!st.empty())
{
if (difv == -oo)
{
difv = v - st.top()[0];
difc = c - st.top()[1];
if (max(difv, difc) == 0) return cout<<-1, 0;
}
else if (iden == -1)
{
int tifv = v - st.top()[0];
int tifc = c - st.top()[1];
/**
* x * dv + dc = x * tv + tc
* x * (dv - tv) = tc - dc
*/
// cout<<"ITIF: "<<i<<" "<<tifv<<" "<<tifc<<"\n";
// cout<<"BONUS: "<<difv<<" "<<difc<<"\n";
if (difv - tifv == 0)
{
if (tifc != difc) return cout<<-1, 0;
else
{
st.push({v, c, 1});
continue;
}
}
else
{
if (tifc == difc) return cout<<-1, 0;
else
{
int dif = tifc - difc;
if (dif % (difv - tifv) != 0) return cout<<-1, 0;
else
{
iden = dif / (difv - tifv);
if (iden <= 0) return cout<<-1, 0;
}
}
}
dif = iden * difv + difc;
// cout<<"HERE???\n";
}
else
{
int tifv = v - st.top()[0];
int tifc = c - st.top()[1];
if (iden * tifv + tifc != dif) return cout<<-1, 0;
}
}
// cout<<"PUSH: "<<i<<" "<<v<<" "<<c<<"\n";
st.push({v, c, 1});
}
else
{
assert(cc == '}');
assert(st.size());
int tifv = v - st.top()[0];
int tifc = c - st.top()[1];
// cout<<"BRUH: "<<st.top()[0]<<" "<<st.top()[1]<<"\n";
/**
* x * tv + tc = 0
* x * tv = -tc
*/
if (tifv == 0)
{
if (tifc == 0) st.pop();
else return cout<<-1, 0;
continue;
}
// cout<<"TIF: "<<tifv<<" "<<tifc<<"\n";
if (tifc % tifv != 0) return cout<<-1, 0;
if (iden == -1)
{
iden = -tifc / tifv;
if (iden <= 0) return cout<<-1, 0;
}
else if (iden != -tifc/tifv) return cout<<-1, 0;
st.pop();
}
}
}
// cout<<"HEH: "<<(st.size() ? st.top()[0] : -1)<<" "<<(st.size() ? st.top()[1] : -1)<<"\n";
}
cout<<max(iden, 1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2
{
}
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
4
{
ss{
ss}
}
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
4
{
tt{
tt}
}
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
4
{
ss{
s}
}
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
4
{
tt{
t}
}
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
4
{
tt{
s}
}
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4
{
tt{
sss}
}
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
4
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
6
{
}
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3832kb
input:
100
{
}
{
}
{
t{
ssssssssssssssssssssssssssssssssssss}
t{
t}
t{
tssssssssssssssssssssssssssssssssssss{
tssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss{
tsssssssssssssssssssssssssssssssssssst}
ttssssssssssssssssssssssssssssssssssss{
ssssssssssssssssssssssssssssssssssssssssss...
output:
-1
result:
wrong answer 1st lines differ - expected: '36', found: '-1'