CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:maweiyin24562
Submission time:2024-11-04 19:39:46 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5, 6details
#20.00 s1, 2, 3, 4, 5, 6details
#30.00 s1, 2, 3, 4, 5, 6details
#40.00 s1, 2, 3, 4, 5, 6details
#50.00 s1, 2, 3, 4, 5, 6details
#60.00 s2, 3, 4, 5, 6details
#70.00 s2, 3, 4, 5, 6details
#80.00 s2, 3, 4, 5, 6details
#90.00 s2, 3, 4, 5, 6details
#100.00 s3, 4, 5, 6details
#110.00 s3, 4, 5, 6details
#120.00 s3, 4, 5, 6details
#130.00 s3, 4, 5, 6details
#140.00 s4, 5, 6details
#150.00 s4, 5, 6details
#160.00 s4, 5, 6details
#170.00 s4, 5, 6details
#180.00 s5, 6details
#190.00 s5, 6details
#200.00 s5, 6details
#210.00 s5, 6details
#220.00 s6details
#230.00 s6details
#240.00 s6details
#250.00 s6details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%lld",&n);
      |         ~~~~~^~~~~~~~~~~

Code

#include <bits/stdc++.h>

using namespace std;

#define IC(c) (int)(c-'A')
#define P(x) (1<<(x))
#define LG(x) log((double)(x))/log(2.0)
#define ll long long

const ll N=509;
const ll LN=10;
ll n,ans;
int total;

//2D Sparse Table + State compression
//+ enum top bottom + double iterator

ll LOG[N];
int st[LN][LN][N][N];

bool check(ll x1,ll y1,ll x2,ll y2){
	ll tx=LOG[x2-x1+1];
	ll ty=LOG[y2-y1+1];
	return (st[tx][ty][x1][y1]|st[tx][ty][x2-P(tx)+1][y1]|
		st[tx][ty][x1][y2-P(ty)+1]|st[tx][ty][x2-P(tx)+1][y2-P(ty)+1])==total;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	freopen("input.txt","r",stdin);
	for(int i=1;i<=500;i++)LOG[i]=LG(i);
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=n;j++){
			char c;
			cin>>c;
			ll id=IC(c);
			st[0][0][i][j]=P(id);
			total=(total|P(id));
		}
	ll t=LOG[n];
	for(ll i=0;i<=t;i++){
		for(ll j=0;j<=t;j++){
			if(i==0&&j==0)continue;
			for(ll r=1;r+P(i)-1<=n;r++){
				for(ll c=1;c+P(j)-1<=n;c++){
					if(i)st[i][j][r][c]=(st[i-1][j][r][c]|st[i-1][j][r+P(i-1)][c]);
					else st[i][j][r][c]=(st[i][j-1][r][c]|st[i][j-1][r][c+P(j-1)]);
				}
            }
		}
	}
	
//	while(true){
//		int x1,y1,x2,y2;
//		cin>>x1>>y1>>x2>>y2;
//		cout<<check(x1,y1,x2,y2)<<endl;
//	}

	for(ll top=1;top<=n;top++){
		for(ll btm=top;btm<=n;btm++){//O(n^2)
			ll l=1,r=1;
			//³ßÈ¡·¨É¨Ãè
			bool tag=false;
			while(r<=n){//O(n)
				while(check(top,l+1,btm,r)&&l<r)l++;
				if(tag)ans+=l;
				else if(check(top,l,btm,r)){
					ans+=l;
					tag=true;
				}
				r++;
			}
		}
	}

	cout<<ans<<endl;
	return 0;
	
}

Test details

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
0

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
0

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
0

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
0

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
1
X

correct output
1

user output
0

Test 6

Group: 2, 3, 4, 5, 6

Verdict:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
0

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
0

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
0

Test 9

Group: 2, 3, 4, 5, 6

Verdict:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
0

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
0

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
0

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
0

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
0

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
0

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
0

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
0

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
0

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
0

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
0

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
0

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
0

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
0

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
0

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
0

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
0