QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413054#6568. Space AlignmentLspeed#AC ✓83ms4080kbC++202.8kb2024-05-17 01:24:452024-05-17 01:24:45

Judging History

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

  • [2024-05-17 01:24:45]
  • 评测
  • 测评结果:AC
  • 用时:83ms
  • 内存:4080kb
  • [2024-05-17 01:24:45]
  • 提交

answer

#include<bits/stdc++.h>
#define x first
#define y second
#define eb emplace_back
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define sz(x) (int)(x).size()
#define make_unique(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())

using namespace std;

typedef long long i64;
//typedef __int128 i128;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef tuple<int,int,int> iii;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

int readInt() { int a; scanf("%d",&a); return a; }
i64 readLong() { i64 a; scanf("%lld",&a); return a; }
char readChar() { char a; scanf(" %c",&a); return a; }
double readDouble() { double a; scanf(" %lf",&a); return a; }
void readString(char *s) { scanf(" %s",s); }

const int mod = 998244353;
int add(int a, int b) { return ((a+=b)>=mod) ? a-mod:a; }
int mul(int a, int b) { return a*1ll*b%mod; }
int pw(int a, int b) {
	int ans = 1, res = a;
	for(int i = 1; i <= b; i*=2, res=mul(res,res)) {
		if(i&b) {
			ans = mul(ans, res);
		}
	}
	return ans;
}

const int N = 105;
int val[N];
char str[N][1005];
int len[N];
int space[N], tab[N];

int main() {
	int n = readInt();
	int cur = 0;
	bool notab = true;
	FOR(i,1,n) {
		readString(str[i]);
		len[i] = strlen(str[i]);
		if(str[i][len[i]-1] == '{') {
			val[i] = cur;
			cur += 1;
		} else {
			cur -= 1;
			val[i] = cur;
		}

		FOR(j,0,len[i]-2) {
			if(str[i][j] == 's') space[i] += 1;
			else {
				tab[i] += 1;
				notab = false;
			}
		}
		//printf("cur %d, space %d, tab %d\n",val[i],space[i],tab[i]);
	}

	FOR(i,1,n) {
		if(val[i] == 0) {
			if(tab[i] != 0 || space[i] != 0) {
				return !printf("-1\n");
			}
		} else {
			if(tab[i] == 0) {
				if(space[i]%val[i] != 0) {
					return !printf("-1\n");
				}
			} 	
		}
	}

	//puts("pass");
	int best = (1<<30);
	bool okay = false;

	FOR(k, 1, 1000000) {
		set<int> ans;
		bool good = true;

		FOR(i, 1, n) {
			if(tab[i] == 0) {
				if(space[i] != k*val[i]) {
					good = false;
					break;
				}
			} else {
				// solve
				if((k*val[i]-space[i])%tab[i] != 0) {
					good = false;
					break;
				}
				if((k*val[i]-space[i]) <= 0) {
					good = false;
					break;
				}

				ans.insert((k*val[i]-space[i])/tab[i]);
			}
		}

		if (!good) {
			//if(k==2) printf("wtf\n");
			continue;
		}
		if(sz(ans) > 1) {
			continue;
		}
		if(*ans.begin() > 0) best = min(best, *ans.begin());
		okay = true;
	}

	if(notab && okay) {
		printf("1\n");
		return 0;
	}

	if(best == (1<<30)) printf("-1\n");
	else printf("%d\n",best);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 4080kb

input:

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

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 4ms
memory: 3708kb

input:

2
{
}

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 4ms
memory: 3696kb

input:

4
{
ss{
ss}
}

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 12ms
memory: 3772kb

input:

4
{
tt{
tt}
}

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 4ms
memory: 3660kb

input:

4
{
ss{
s}
}

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 21ms
memory: 3716kb

input:

4
{
tt{
t}
}

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 12ms
memory: 3992kb

input:

4
{
tt{
s}
}

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0
Accepted
time: 12ms
memory: 3768kb

input:

4
{
tt{
sss}
}

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 12ms
memory: 3800kb

input:

4
{
tt{
ssss}
}

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 13ms
memory: 3872kb

input:

6
{
}
{
tt{
ssss}
}

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Accepted
time: 22ms
memory: 3888kb

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: 83ms
memory: 3896kb

input:

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

output:

20

result:

ok single line: '20'

Test #13:

score: 0
Accepted
time: 19ms
memory: 3768kb

input:

4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

999

result:

ok single line: '999'