QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207987#6568. Space AlignmentThallium54#AC ✓1ms7832kbC++201.9kb2023-10-09 02:21:592023-10-09 02:21:59

Judging History

你现在查看的是最新测评结果

  • [2023-10-09 02:21:59]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:7832kb
  • [2023-10-09 02:21:59]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>

 
const int N = 1e5 + 100;
const int inf = 1e9;
const ll mod =  9302023;

int a[N], b[N], d[N];
int n;
string s[N];


inline void check(int x)
{
	int k = -1;
	for(int i = 0; i < n; i++)
	{
		if(d[i] == 0 && (x*a[i] + b[i]) != 0)
		{
			cout << -1 << endl;
			exit(0);
		}
		if(d[i] == 0)
			continue;
		//cout << i << ' ' << x << ' ' << d[i] << ' ' << k << endl;
		// d[i] != 0
		if((x*a[i] + b[i])%d[i] != 0)
		{
			cout << -1 << endl;
			exit(0);
		}
		if(k == -1)
		{
			k = (x*a[i] + b[i]) / d[i];
			continue;
		}
		if(k != (x*a[i] + b[i]) / d[i])
		{
			cout << -1 << endl;
			exit(0);
		}
	
	}
	if(k == 0 || x == 0)
		cout << -1 << endl;
	else
		cout << x << endl;
	exit(0);
}


int main()
{
	
	cin >> n;
	int k = 0;
	for(int i = 0; i < n; i++)
	{
		cin >> s[i];
		int m = s[i].size();
		
		if(s[i][m-1] == '}')
			k--;
		for(int j = 0; j < m-1; j++)
		{
			if(s[i][j] == 's')
				b[i]++;
			else
				a[i]++;	
		}
		d[i] = k;
		
		if(s[i][m-1] == '{')
			k++;
			
	}
	
	
	for(int i = 0; i < n; i++)
	{
		if(d[i] == 0)
		{
			if(b[i] != 0)
			{
				cout << -1 << endl;
				exit(0);
			}
			if(a[i] != 0)
			{
				check(0);
			}
			continue;
		}
		for(int j = i+1; j < n; j++)
		{
			if(d[j] == 0)
			{
				if(b[j] != 0)
				{
					cout << -1 << endl;
					exit(0);
				}
				if(a[j] != 0)
				{
					check(0);
				}
				continue;
			}

			
			int A = a[i]*d[j], B = b[i]*d[j];
			int A2 = a[j]*d[i], B2 = b[j]*d[i];
			if(A == A2 && B == B2)
				continue;
			if(A == A2)
			{
				cout << -1 << endl;
				exit(0);
			}	
			
			check((B2-B)/(A-A2));
			
		}
	}
		
	cout << 1 << endl;	
		
		
    return 0;
}





Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6844kb

input:

10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7208kb

input:

2
{
}

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 6780kb

input:

4
{
ss{
ss}
}

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 1ms
memory: 6848kb

input:

4
{
tt{
tt}
}

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 6848kb

input:

4
{
ss{
s}
}

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 7272kb

input:

4
{
tt{
t}
}

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7508kb

input:

4
{
tt{
s}
}

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7724kb

input:

4
{
tt{
sss}
}

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 1ms
memory: 6868kb

input:

4
{
tt{
ssss}
}

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 1ms
memory: 6804kb

input:

6
{
}
{
tt{
ssss}
}

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Accepted
time: 1ms
memory: 7832kb

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: 7044kb

input:

100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...

output:

20

result:

ok single line: '20'

Test #13:

score: 0
Accepted
time: 1ms
memory: 6796kb

input:

4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

999

result:

ok single line: '999'