oj.uz

Submission #926268

# Submission time Handle Problem Language Result Execution time Memory
926268 2024-02-12T18:08:41 Z samek08 Cards (LMIO19_korteles) C++14
36 / 100
 1000 ms 50640 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

struct Element
{
	string n1, n2, n3, n4;
	bool operator < (const Element &element) const
	{
		//return n1 < element.n1 || n2 < element.n2 || n3 < element.n3 || n4 < element.n4;
		if(n1 == element.n1)
		{
			if(n2 == element.n2)
			{
				if(n3 == element.n3)
				{
					return n4 < element.n4;
				}
				return n3 < element.n3;
			}
			return n2 < element.n2;
		}
		return n1 < element.n1;
	}
}; 

const int MAXN = 5e5+5, p = 2137, mod = 1e9+7;
int n = 0;
ll wyn = 0;
char A[4][MAXN];
unordered_map<int,int> S1;
unordered_map<int,int> S2;
unordered_map<int,int> S3;
unordered_map<int,int> S4;
int POW[10];

inline void dodaj1(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S1.find(x) != S1.end()) ++S1[x];
	else S1[x] = 1;
}

inline void dodaj2(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S2.find(x) != S2.end()) ++S2[x];
	else S2[x] = 1;
}

inline void dodaj3(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S3.find(x) != S3.end()) ++S3[x];
	else S3[x] = 1;
}

inline void dodaj4(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S4.find(x) != S4.end()) ++S4[x];
	else S4[x] = 1;
}

inline int licz1(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S1.find(x) != S1.end()) return S1[x];
	return 0;
}

inline int licz2(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S2.find(x) != S2.end()) return S2[x];
	return 0;
}

inline int licz3(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S3.find(x) != S3.end()) return S3[x];
	return 0;
}

inline int licz4(string el)
{
	int x = 0;
	rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
	if(auto it = S4.find(x) != S4.end()) return S4[x];
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	POW[0] = 1;
	for(int i = 1; i < 10; ++i) POW[i] = ((ll)POW[i-1]*(ll)p) % (ll)mod;

	cin >> n;
	rep(i,n) rep(j,4) cin >> A[j][i];

	rep(i,n)
	{
		string z0, z1, z2, z3, dod = "z";

		int res = 0;

		z0.pb(A[0][i]), z0.pb(A[2][i]);
		z1.pb(A[1][i]), z1.pb(A[3][i]);
		z2.pb(A[0][i]), z2.pb(A[1][i]);
		z3.pb(A[2][i]), z3.pb(A[3][i]);

		res += licz1(z0+dod+dod+dod);
		res += licz1(dod+z1+dod+dod);
		res += licz1(dod+dod+z2+dod);
		res += licz1(dod+dod+dod+z3);

		res -= licz2(z0+z1+dod+dod);
		res -= licz2(z0+dod+z2+dod);
		res -= licz2(z0+dod+dod+z3);
		res -= licz2(dod+z1+z2+dod);
		res -= licz2(dod+z1+dod+z3);
		res -= licz2(dod+dod+z2+z3);

		res += licz3(z0+z1+z2+dod);
		res += licz3(z0+z1+dod+z3);
		res += licz3(z0+dod+z2+z3);
		res += licz3(dod+z1+z2+z3); 

		res -= licz4(z0+z1+z2+z3); 


		wyn += res;

		z0.clear(), z1.clear(), z2.clear(), z3.clear();
		z0.pb(A[1][i]), z0.pb(A[3][i]);
		z1.pb(A[0][i]), z1.pb(A[2][i]);
		z2.pb(A[2][i]), z2.pb(A[3][i]);
		z3.pb(A[0][i]), z3.pb(A[1][i]);

		dodaj1(z0+dod+dod+dod);
		dodaj1(dod+z1+dod+dod);
		dodaj1(dod+dod+z2+dod);
		dodaj1(dod+dod+dod+z3);

		dodaj2(z0+z1+dod+dod);
		dodaj2(z0+dod+z2+dod);
		dodaj2(z0+dod+dod+z3);
		dodaj2(dod+z1+z2+dod);
		dodaj2(dod+z1+dod+z3);
		dodaj2(dod+dod+z2+z3);

		dodaj3(z0+z1+z2+dod);
		dodaj3(z0+z1+dod+z3);
		dodaj3(z0+dod+z2+z3);
		dodaj3(dod+z1+z2+z3); 

		dodaj4(z0+z1+z2+z3); 
	}

	cout << wyn << '\n';

	return 0;
}

Compilation message

korteles.cpp: In function 'void dodaj1(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:43:2: note: in expansion of macro 'rep'
   43 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:44:10: warning: unused variable 'it' [-Wunused-variable]
   44 |  if(auto it = S1.find(x) != S1.end()) ++S1[x];
      |          ^~
korteles.cpp: In function 'void dodaj2(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:51:2: note: in expansion of macro 'rep'
   51 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:52:10: warning: unused variable 'it' [-Wunused-variable]
   52 |  if(auto it = S2.find(x) != S2.end()) ++S2[x];
      |          ^~
korteles.cpp: In function 'void dodaj3(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:59:2: note: in expansion of macro 'rep'
   59 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:60:10: warning: unused variable 'it' [-Wunused-variable]
   60 |  if(auto it = S3.find(x) != S3.end()) ++S3[x];
      |          ^~
korteles.cpp: In function 'void dodaj4(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:67:2: note: in expansion of macro 'rep'
   67 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:68:10: warning: unused variable 'it' [-Wunused-variable]
   68 |  if(auto it = S4.find(x) != S4.end()) ++S4[x];
      |          ^~
korteles.cpp: In function 'int licz1(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:75:2: note: in expansion of macro 'rep'
   75 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:76:10: warning: unused variable 'it' [-Wunused-variable]
   76 |  if(auto it = S1.find(x) != S1.end()) return S1[x];
      |          ^~
korteles.cpp: In function 'int licz2(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:83:2: note: in expansion of macro 'rep'
   83 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:84:10: warning: unused variable 'it' [-Wunused-variable]
   84 |  if(auto it = S2.find(x) != S2.end()) return S2[x];
      |          ^~
korteles.cpp: In function 'int licz3(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:91:2: note: in expansion of macro 'rep'
   91 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:92:10: warning: unused variable 'it' [-Wunused-variable]
   92 |  if(auto it = S3.find(x) != S3.end()) return S3[x];
      |          ^~
korteles.cpp: In function 'int licz4(std::string)':
korteles.cpp:4:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a,b) for(int a = 0; a < (b); ++a)
      |                                   ^
korteles.cpp:99:2: note: in expansion of macro 'rep'
   99 |  rep(i,el.size()) x = ((ll)x+(ll)POW[i]*(ll)(el[i])) % (ll)mod;
      |  ^~~
korteles.cpp:100:10: warning: unused variable 'it' [-Wunused-variable]
  100 |  if(auto it = S4.find(x) != S4.end()) return S4[x];
      |          ^~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 10 ms 1628 KB Output is correct
9 Correct 10 ms 1372 KB Output is correct
10 Correct 10 ms 1372 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 50640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 255 ms 18408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 6 ms 860 KB Output is correct
4 Correct 10 ms 1628 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 10 ms 1372 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Execution timed out 1043 ms 50640 KB Time limit exceeded
13 Halted 0 ms 0 KB -