oj.uz

Submission #160778

# Submission time Handle Problem Language Result Execution time Memory
160778 2019-10-29T21:47:28 Z luciocf PIN (CEOI10_pin) C++14
30 / 100
 1000 ms 8952 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4+10;

long long ans;

int qtd[40][40][40][40];
char s[maxn][4];

void add_0(int ind, int x_0, int x_1, int x_2, int x_3)
{
	for (int a = 0; a < 40; a++)
		for (int b = 0; b < 40; b++)
			for (int c = 0; c < 40; c++)
				for (int d = 0; d < 40; d++)
					ans += 1ll*qtd[a][b][c][d];
}

void add_1(int ind, int x_0, int x_1, int x_2, int x_3)
{
	for (int mask = 0; mask < (1<<4); mask++)
	{
		if (__builtin_popcount(mask) != 1) continue;

		int pos;

		for (int i = 0; i < 4; i++)
			if (mask&(1<<i))
				pos = i;

		int x_0 = ( (s[ind][0] >= '0' && s[ind][0] <= '9') ? (26 + (int)(s[ind][0]-'0')) : (int)(s[ind][0]-'a'));
		int x_1 = ( (s[ind][1] >= '0' && s[ind][1] <= '9') ? (26 + (int)(s[ind][1]-'0')) : (int)(s[ind][1]-'a'));
		int x_2 = ( (s[ind][2] >= '0' && s[ind][2] <= '9') ? (26 + (int)(s[ind][2]-'0')) : (int)(s[ind][2]-'a'));
		int x_3 = ( (s[ind][3] >= '0' && s[ind][3] <= '9') ? (26 + (int)(s[ind][3]-'0')) : (int)(s[ind][3]-'a'));

		for (int a = 0; a < 40; a++)
		{
			for (int b = 0; b < 40; b++)
			{
				for (int c = 0; c < 40; c++)
				{
					if (pos == 0)
						ans += 1ll*qtd[x_0][a][b][c];
					else if (pos == 1)
						ans += 1ll*qtd[a][x_1][b][c];
					else if (pos == 2)
						ans += 1ll*qtd[a][b][x_2][c];
					else
						ans += 1ll*qtd[a][b][x_3][c];
				}
			}
		}
	}
}

void add_2(int ind, int x_0, int x_1, int x_2, int x_3)
{
	for (int mask = 0; mask < (1<<4); mask++)
	{
		if (__builtin_popcount(mask) != 2) continue;

		int pos_0 = -1, pos_1;

		for (int i = 0; i < 4; i++)
		{
			if (mask&(1<<i) && pos_0 == -1)
				pos_0 = i;
			else if (mask&(1<<i))
				pos_1 = i;
		}

		for (int a = 0; a < 40; a++)
		{
			for (int b = 0; b < 40; b++)
			{
				if (pos_0 == 0 && pos_1 == 1)
					ans += 1ll*qtd[x_0][x_1][a][b];
				else if (pos_0 == 0 && pos_1 == 2)
					ans += 1ll*qtd[x_0][a][x_2][b];
				else if (pos_0 == 0 && pos_1 == 3)
					ans += 1ll*qtd[x_0][a][b][x_3];
				else if (pos_0 == 1 && pos_1 == 2)
					ans += 1ll*qtd[a][x_1][x_2][b];
				else if (pos_0 == 1 && pos_1 == 3)
					ans += 1ll*qtd[a][x_1][b][x_3];
				else if (pos_0 == 2 && pos_1 == 3)
					ans += 1ll*qtd[a][b][x_2][x_3];
			}
		}
	}
}

void add_3(int ind, int x_0, int x_1, int x_2, int x_3)
{
	for (int mask = 0; mask < (1<<4); mask++)
	{
		if (__builtin_popcount(mask) != 3) continue;

		int pos_0 = -1, pos_1 = -1, pos_2;

		for (int i = 0; i < 4; i++)
		{
			if (mask&(1<<i) && pos_0 == -1)
				pos_0 = i;
			else if (mask&(1<<i) && pos_1 == -1)
				pos_1 = i;
			else if (mask&(1<<i))
				pos_2 = i;
		}

		for (int a = 0; a < 40; a++)
		{
			if (pos_0 == 0 && pos_1 == 1 && pos_2 == 2)
				ans += 1ll*qtd[x_0][x_1][x_2][a];
			else if (pos_0 == 0 && pos_1 == 1 && pos_2 == 3)
				ans += 1ll*qtd[x_0][x_1][a][x_3];
			else if (pos_0 == 0 && pos_1 == 2 && pos_2 == 3)
				ans += 1ll*qtd[x_0][a][x_2][x_3];
			else if (pos_0 == 1 && pos_1 == 2 && pos_2 == 3)
				ans += 1ll*qtd[a][x_1][x_2][x_3];
		}
	}
}

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

	for (int i = 0; i < n; i++)
	{
		vector<int> v;

		for (int j = 0; j < 4; j++)
		{
			scanf(" %c", &s[i][j]);

			int x = (int)s[i][j]-(int)'a';

			if (s[i][j] >= '0' && s[i][j] <= '9')
				x = 26+(int)(s[i][j]-'0');

			v.push_back(x);
		}

		qtd[v[0]][v[1]][v[2]][v[3]]++;
	}

	for (int i = 0; i < n; i++)
	{
		vector<int> v;

		for (int j = 0; j < 4; j++)
		{
			int x = (int)s[i][j]-(int)'a';

			if (s[i][j] >= '0' && s[i][j] <= '9')
				x = 26+(int)(s[i][j]-'0');

			v.push_back(x);
		}

		qtd[v[0]][v[1]][v[2]][v[3]]--;

		if (d == 1) add_3(i, v[0], v[1], v[2], v[3]);
		else if (d == 2) add_2(i, v[0], v[1], v[2], v[3]);
		else if (d == 3) add_1(i, v[0], v[1], v[2], v[3]);
		else add_0(i, v[0], v[1], v[2], v[3]);

	}

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

Compilation message

pin.cpp: In function 'int main()':
pin.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &d);
  ~~~~~^~~~~~~~~~~~~~~~~
pin.cpp:138:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~
pin.cpp: In function 'void add_1(int, int, int, int, int)':
pin.cpp:44:6: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
      if (pos == 0)
      ^~
pin.cpp: In function 'void add_2(int, int, int, int, int)':
pin.cpp:82:34: warning: 'pos_1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     else if (pos_0 == 0 && pos_1 == 3)
                            ~~~~~~^~~~
pin.cpp: In function 'void add_3(int, int, int, int, int)':
pin.cpp:121:38: warning: 'pos_2' may be used uninitialized in this function [-Wmaybe-uninitialized]
    else if (pos_0 == 1 && pos_1 == 2 && pos_2 == 3)
             ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2040 KB Output is correct
2 Incorrect 52 ms 1912 KB Output isn't correct
3 Execution timed out 1090 ms 1912 KB Time limit exceeded
4 Correct 29 ms 2296 KB Output is correct
5 Correct 35 ms 2424 KB Output is correct
6 Incorrect 756 ms 2396 KB Output isn't correct
7 Incorrect 593 ms 2168 KB Output isn't correct
8 Correct 39 ms 2296 KB Output is correct
9 Correct 58 ms 2424 KB Output is correct
10 Execution timed out 1081 ms 2432 KB Time limit exceeded
11 Incorrect 774 ms 2396 KB Output isn't correct
12 Execution timed out 1088 ms 2424 KB Time limit exceeded
13 Execution timed out 1079 ms 2296 KB Time limit exceeded
14 Execution timed out 1075 ms 2296 KB Time limit exceeded
15 Execution timed out 1075 ms 2424 KB Time limit exceeded
16 Correct 56 ms 8824 KB Output is correct
17 Execution timed out 1092 ms 8952 KB Time limit exceeded
18 Execution timed out 1085 ms 8952 KB Time limit exceeded
19 Execution timed out 1080 ms 8924 KB Time limit exceeded
20 Execution timed out 1074 ms 8952 KB Time limit exceeded