QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #239024 | #6568. Space Alignment | ElyesChaabouni# | WA | 0ms | 3852kb | C++14 | 3.3kb | 2023-11-04 18:08:36 | 2023-11-04 18:08:36 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#define INV_2 499122177
#define INF 1000000000
#define PI 3.14159265358979323846
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
using namespace std;
vector<pair<long long, long long> >v[1005];
vector<pair<pair<long long, long long>, long long> >vv;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
long long n;
cin >> n;cin.ignore();
string s;
long long cu=0;
long long nb_t_tot=0;
long long xx=-1;
for(long long i = 0; i < n; i++)
{
getline(cin, s);
//cout << s << endl;
long long nb_s=0, nb_t=0;
for(long long j = 0; j< s.length(); j++)
{
if(s[j]=='s')
nb_s++;
else if(s[j]=='t')
nb_t++;
}
if(s.back() == '}')
cu--;
//cout << nb_s << ' ' << nb_t << ' ' <<cu << '\n';
v[cu].push_back(make_pair(nb_s, nb_t));
vv.push_back(make_pair(make_pair(nb_s, nb_t), cu));
if(cu==0 && nb_t+nb_s!=0)
{
cout << "-1\n";
return 0;
}
if(cu!=0 && nb_t==0 && xx==-1)
{
if(nb_s%cu)
{
//cout << "here1\n";
cout << "-1\n";
return 0;
}
xx=nb_s/cu;
}
if(s.back() == '{')
cu++;
nb_t_tot+=nb_t;
}
if(nb_t_tot==0)
{
cout << "1\n";
return 0;
}
long long alpha=-1;
if(xx==-1)
{
for(long long i = 0; i < n && alpha==-1; i++)
{
if(vv[i].second==0)
continue;
for(long long j = 0; j < n && alpha==-1; j++)
{
if(vv[j].second==0)
continue;
long long x, y, x1, y1;
x=vv[i].first.first;
x*=vv[j].second;
y=vv[i].first.second;
y*=vv[j].second;
x1=vv[j].first.first;
x1*=vv[i].second;
y1=vv[j].first.second;
y1*=vv[i].second;
if(y==y1)
{
if(x!=x1)
{
//cout << "here2\n";
cout << "-1\n";
return 0;
}
}
else if(x==x1)
{
if(y!=y1)
{
cout << "-1\n";
return 0;
}
}
else if((x1-x)%(y-y1))
{
//cout << "here3\n";
cout << "-1\n";
return 0;
}
else
{
alpha = (x1-x)%(y-y1);
if(alpha <= 0)
{
//cout << "here4\n";
cout << "-1\n";
return 0;
}
xx=vv[i].first.first+alpha*vv[i].first.second;
if(xx <= 0)
{
//cout << "here5\n";
cout << "-1\n";
return 0;
}
}
}
}
}
if(xx == -1)
{
cout << "1\n";
return 0;
}
if(alpha == -1)
{
for(long long i = 0; i < n && alpha==-1; i++)
{
if(vv[i].second==0)
continue;
long long x, y, x1, y1;
x=vv[i].first.first;
y=vv[i].first.second;
if(y==0)
continue;
if((vv[i].second*xx-x)%y)
{
//cout << "here6\n";
cout << "-1\n";
return 0;
}
alpha = (vv[i].second*xx-x)/y;
//cout << i << '\n';
}
}
//cout << xx << ' ' << alpha << '\n';
for(long long i = 0; i < n; i++)
{
long long x, y, x1, y1;
x=vv[i].first.first;
y=vv[i].first.second;
if(x+alpha*y!=xx*vv[i].second)
{
//cout << "here7\n";
cout << "-1\n";
return 0;
}
}
if(alpha==0)
alpha = -1;
cout << alpha << '\n';
}
//07-02-46
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
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: 3576kb
input:
2
{
}
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
4
{
ss{
ss}
}
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
4
{
tt{
tt}
}
output:
1
result:
ok single line: '1'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3508kb
input:
4
{
ss{
s}
}
output:
1
result:
wrong answer 1st lines differ - expected: '-1', found: '1'