oj.uz

Submission #160779

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

using namespace std;

const int maxn = 5e4+10;

long long ans;

int qtd[36][36][36][36];
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 < 36; a++)
		for (int b = 0; b < 36; b++)
			for (int c = 0; c < 36; c++)
				for (int d = 0; d < 36; 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 < 36; a++)
		{
			for (int b = 0; b < 36; b++)
			{
				for (int c = 0; c < 36; 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 < 36; a++)
		{
			for (int b = 0; b < 36; 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 < 36; 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 6 ms 1656 KB Output is correct
2 Incorrect 39 ms 1656 KB Output isn't correct
3 Execution timed out 1069 ms 1656 KB Time limit exceeded
4 Correct 26 ms 1784 KB Output is correct
5 Correct 32 ms 1784 KB Output is correct
6 Incorrect 566 ms 1844 KB Output isn't correct
7 Incorrect 446 ms 1848 KB Output isn't correct
8 Correct 33 ms 1784 KB Output is correct
9 Correct 52 ms 1912 KB Output is correct
10 Execution timed out 1075 ms 1912 KB Time limit exceeded
11 Incorrect 606 ms 1848 KB Output isn't correct
12 Execution timed out 1085 ms 1912 KB Time limit exceeded
13 Execution timed out 1075 ms 1788 KB Time limit exceeded
14 Execution timed out 1079 ms 1784 KB Time limit exceeded
15 Execution timed out 1068 ms 1912 KB Time limit exceeded
16 Correct 60 ms 7032 KB Output is correct
17 Execution timed out 1076 ms 7032 KB Time limit exceeded
18 Execution timed out 1071 ms 7036 KB Time limit exceeded
19 Execution timed out 1074 ms 7032 KB Time limit exceeded
20 Execution timed out 1079 ms 7160 KB Time limit exceeded