Submission #594897

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
594897	2022-07-13T06:31:59 Z	jwvg0425	Misspelling (JOI22_misspelling)	C++17	28 / 100	139 ms	42648 KB

misspelling

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <array>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e9 + 7)

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int n, m;
i64 table[35][205][205];
vector<ii> conds[205];

i64 solve(int pch, int l, int r)
{
	if (r == n + 1)
		return 1;

	auto& res = table[pch][l][r];

	if (res != -1)
		return res;

	res = solve(pch, l, r + 1) % MOD;

	// 바꾸는 경우. l 이후에서 시작하고 r포함하는 조건들을 봐야 한다
	int up = 0, down = 0;
	for (int cl = l + 1; cl <= r; cl++)
	{
		for (auto& c : conds[cl])
		{
			if (c.xx < r)
				continue;

			if (c.yy > 0)
				up++;
			else
				down++;
		}
	}

	if (up > 0 && down > 0)
	{
		return res;
	}
	else if (up > 0)
	{
		for (int nch = pch + 1; nch < 26; nch++)
			res = (res + solve(nch, r, r + 1)) % MOD;
	}
	else if (down > 0)
	{
		for (int nch = 0; nch < pch; nch++)
			res = (res + solve(nch, r, r + 1)) % MOD;
	}
	else
	{
		for (int nch = 0; nch < 26; nch++)
		{
			if (nch == pch)
				continue;

			res = (res + solve(nch, r, r + 1)) % MOD;
		}
	}

	return res;
}

int main()
{
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);

		if (a < b)
			conds[a + 1].emplace_back(b, -1);
		else
			conds[b + 1].emplace_back(a, 1);
	}

	memset(table, -1, sizeof(table));

	i64 ans = 0;
	for (int ch = 0; ch < 26; ch++)
		ans = (ans + solve(ch, 1, 2)) % MOD;

	printf("%lld\n", ans);

	return 0;
}

Compilation message

misspelling.cpp: In function 'int main()':
misspelling.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
misspelling.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	11732 KB	Output is correct
2	Correct	5 ms	11732 KB	Output is correct
3	Correct	7 ms	11776 KB	Output is correct
4	Correct	5 ms	11732 KB	Output is correct
5	Correct	5 ms	11704 KB	Output is correct
6	Correct	5 ms	11732 KB	Output is correct
7	Correct	5 ms	11732 KB	Output is correct
8	Correct	5 ms	11700 KB	Output is correct
9	Correct	5 ms	11732 KB	Output is correct
10	Correct	6 ms	11732 KB	Output is correct
11	Correct	5 ms	11732 KB	Output is correct
12	Correct	6 ms	11708 KB	Output is correct
13	Correct	5 ms	11712 KB	Output is correct
14	Correct	6 ms	11732 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	11732 KB	Output is correct
2	Correct	5 ms	11732 KB	Output is correct
3	Correct	7 ms	11776 KB	Output is correct
4	Correct	5 ms	11732 KB	Output is correct
5	Correct	5 ms	11704 KB	Output is correct
6	Correct	5 ms	11732 KB	Output is correct
7	Correct	5 ms	11732 KB	Output is correct
8	Correct	5 ms	11700 KB	Output is correct
9	Correct	5 ms	11732 KB	Output is correct
10	Correct	6 ms	11732 KB	Output is correct
11	Correct	5 ms	11732 KB	Output is correct
12	Correct	6 ms	11708 KB	Output is correct
13	Correct	5 ms	11712 KB	Output is correct
14	Correct	6 ms	11732 KB	Output is correct
15	Correct	131 ms	11732 KB	Output is correct
16	Correct	91 ms	11732 KB	Output is correct
17	Correct	17 ms	11860 KB	Output is correct
18	Correct	14 ms	11800 KB	Output is correct
19	Correct	44 ms	11732 KB	Output is correct
20	Correct	28 ms	11836 KB	Output is correct
21	Correct	7 ms	11836 KB	Output is correct
22	Correct	139 ms	12028 KB	Output is correct
23	Correct	104 ms	11812 KB	Output is correct
24	Correct	15 ms	11832 KB	Output is correct
25	Correct	69 ms	11824 KB	Output is correct

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	11732 KB	Output is correct
2	Correct	5 ms	11732 KB	Output is correct
3	Correct	5 ms	11732 KB	Output is correct
4	Correct	5 ms	11704 KB	Output is correct
5	Runtime error	93 ms	42648 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	11732 KB	Output is correct
2	Correct	5 ms	11732 KB	Output is correct
3	Correct	7 ms	11776 KB	Output is correct
4	Correct	5 ms	11732 KB	Output is correct
5	Correct	5 ms	11704 KB	Output is correct
6	Correct	5 ms	11732 KB	Output is correct
7	Correct	5 ms	11732 KB	Output is correct
8	Correct	5 ms	11700 KB	Output is correct
9	Correct	5 ms	11732 KB	Output is correct
10	Correct	6 ms	11732 KB	Output is correct
11	Correct	5 ms	11732 KB	Output is correct
12	Correct	6 ms	11708 KB	Output is correct
13	Correct	5 ms	11712 KB	Output is correct
14	Correct	6 ms	11732 KB	Output is correct
15	Correct	131 ms	11732 KB	Output is correct
16	Correct	91 ms	11732 KB	Output is correct
17	Correct	17 ms	11860 KB	Output is correct
18	Correct	14 ms	11800 KB	Output is correct
19	Correct	44 ms	11732 KB	Output is correct
20	Correct	28 ms	11836 KB	Output is correct
21	Correct	7 ms	11836 KB	Output is correct
22	Correct	139 ms	12028 KB	Output is correct
23	Correct	104 ms	11812 KB	Output is correct
24	Correct	15 ms	11832 KB	Output is correct
25	Correct	69 ms	11824 KB	Output is correct
26	Runtime error	24 ms	28968 KB	Execution killed with signal 11
27	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	11732 KB	Output is correct
2	Correct	5 ms	11732 KB	Output is correct
3	Correct	7 ms	11776 KB	Output is correct
4	Correct	5 ms	11732 KB	Output is correct
5	Correct	5 ms	11704 KB	Output is correct
6	Correct	5 ms	11732 KB	Output is correct
7	Correct	5 ms	11732 KB	Output is correct
8	Correct	5 ms	11700 KB	Output is correct
9	Correct	5 ms	11732 KB	Output is correct
10	Correct	6 ms	11732 KB	Output is correct
11	Correct	5 ms	11732 KB	Output is correct
12	Correct	6 ms	11708 KB	Output is correct
13	Correct	5 ms	11712 KB	Output is correct
14	Correct	6 ms	11732 KB	Output is correct
15	Correct	131 ms	11732 KB	Output is correct
16	Correct	91 ms	11732 KB	Output is correct
17	Correct	17 ms	11860 KB	Output is correct
18	Correct	14 ms	11800 KB	Output is correct
19	Correct	44 ms	11732 KB	Output is correct
20	Correct	28 ms	11836 KB	Output is correct
21	Correct	7 ms	11836 KB	Output is correct
22	Correct	139 ms	12028 KB	Output is correct
23	Correct	104 ms	11812 KB	Output is correct
24	Correct	15 ms	11832 KB	Output is correct
25	Correct	69 ms	11824 KB	Output is correct
26	Correct	5 ms	11732 KB	Output is correct
27	Correct	5 ms	11732 KB	Output is correct
28	Correct	5 ms	11732 KB	Output is correct
29	Correct	5 ms	11704 KB	Output is correct
30	Runtime error	93 ms	42648 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Submission #594897

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 29.0

Subtask #4 0 / 32.0

Subtask #5 0 / 11.0

Subtask #1
8.0 / 8.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 29.0

Subtask #4
0 / 32.0

Subtask #5
0 / 11.0