QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112254#6568. Space AlignmentITMO_pengzoo#AC ✓7ms3788kbC++204.0kb2023-06-10 22:43:572023-06-10 22:44:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-10 22:44:00]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:3788kb
  • [2023-06-10 22:43:57]
  • 提交

answer

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <stdio.h>
#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}

template<size_t index, typename T>
std::ostream& print_tuple(std::ostream& out, const T& t) {
    if constexpr (index == std::tuple_size<T>::value) {
        out << ")";
        return out;
    } else {
        if (index > 0) {
            out << ", ";
        } else {
            out << "(";
        }
        out << std::get<index>(t);
        return print_tuple<index + 1, T>(out, t);
    }
}

template<typename ...T>
std::ostream& operator<<(std::ostream& out, const std::tuple<T...>& t) {
    return print_tuple<0, std::tuple<T...>>(out, t);
}

template<typename Container, typename = decltype(std::begin(std::declval<Container>()))>
typename std::enable_if<!std::is_same<Container, std::string>::value, std::ostream&>::type
operator<<(std::ostream& out, const Container& container) {
    out << "{";
    for (auto it = container.begin(); it != container.end(); ++it) {
        if (it != container.begin()) {
            out << ", ";
        }
        out << *it;
    }
    out << "}";
    return out;
}

template<typename T>
bool smin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool smax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;

void run() {
	fastIO;

	int n;
	std::cin >> n;

	std::vector<std::string> lines(n);
	for (int i = 0; i < n; ++i) {
		std::cin >> lines[i];
	}

	std::map<int, std::vector<std::pair<int, int>>> cnt;
	int lvl = 0;
	for (auto s : lines) {
		int cntT = 0, cntS = 0;
		for (int i = 0; i < (int)s.size() - 1; ++i) {
			if (s[i] == 's') {
				++cntS;
			} else {
				++cntT;
			}
		}
		if (s.back() == '}') {
			--lvl;
		}
		cnt[lvl].push_back(std::make_pair(cntS, cntT));
		// std::cout << lvl << ' ' << cntS << ' ' << cntT << std::endl;
		if (s.back() == '{') {
			++lvl;
		}
	}

	for (int x = 1; x <= 100000; ++x) {
		ll fixedI = -1;
		bool isBad = false;
		for (auto&[k, v] : cnt) {
			if (isBad) {
				break;
			}
			for (auto[s, t] : v) {
				ll left = s + 1ll * x * t;
				if (k == 0 && left > 0) {
					isBad = true;
					break;
				}
				if (k == 0) {
					continue;
				}
				if (left % k != 0) {
					isBad = true;
					break;
				}

				ll i = left / k;
				// debug(left);
				// debug(i);
				if (fixedI == -1) {
					fixedI = i;
				} else if (fixedI != i) {
					isBad = true;
					break;
				}
			}
		}

		if (!isBad) {
			printf("%d\n", x);
			return;
		}
	}

	printf("-1\n");
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    #ifdef PERVEEVM_LOCAL
        auto start = std::chrono::high_resolution_clock::now();
    #endif

    run();

    #ifdef PERVEEVM_LOCAL
        auto end = std::chrono::high_resolution_clock::now();
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

2
{
}

output:

1

result:

ok single line: '1'

Test #3:

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

input:

4
{
ss{
ss}
}

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

4
{
tt{
tt}
}

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 5ms
memory: 3588kb

input:

4
{
ss{
s}
}

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

4
{
tt{
t}
}

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

4
{
tt{
s}
}

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0
Accepted
time: 7ms
memory: 3556kb

input:

4
{
tt{
sss}
}

output:

-1

result:

ok single line: '-1'

Test #9:

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

input:

4
{
tt{
ssss}
}

output:

2

result:

ok single line: '2'

Test #10:

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

input:

6
{
}
{
tt{
ssss}
}

output:

2

result:

ok single line: '2'

Test #11:

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

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

input:

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

output:

20

result:

ok single line: '20'

Test #13:

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

input:

4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

999

result:

ok single line: '999'