QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631797#515. A Random Problemchuchu#WA 83ms951012kbC++142.4kb2024-10-12 10:19:492024-10-12 10:19:50

Judging History

你现在查看的是最新测评结果

  • [2024-10-12 10:19:50]
  • 评测
  • 测评结果:WA
  • 用时:83ms
  • 内存:951012kb
  • [2024-10-12 10:19:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int short
typedef vector<int> vi;
#define pb push_back

pair<int, int> cnt[11][11][1001][1001];
int cnt1[11][11][1001][1001];
int cnt2[11][11][1001][1001];

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < 11; i++){
		for(int j = 0; j < 11; j++){
			for(int k = 0; k < 1001; k++){
				for(int l = 0; l < 1001; l++){
					cnt[i][j][k][l].first = -1;
					cnt[i][j][k][l].second = -1;
					cnt1[i][j][k][l] = -1;
					cnt2[i][j][k][l] = -1;
				}
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			for(int k = j + 1; k < n; k++){
				//cnt[a[i]][a[j]][j - i][k - j]
				//0
				if(cnt[a[i]][a[j]][j - i][k - j].first == -1){
					cnt[a[i]][a[j]][j - i][k - j].first = a[k];
					cnt[a[i]][a[j]][j - i][k - j].second = 1;
				}
				else if(cnt[a[i]][a[j]][j - i][k - j].first != -2){
					if(cnt[a[i]][a[j]][j - i][k - j].first != a[k]){
						cnt[a[i]][a[j]][j - i][k - j].first = -2;
					}
					cnt[a[i]][a[j]][j - i][k - j].second++;
				}
				//1
				if(cnt1[a[i]][a[k]][j - i][k - j] == -1){
					cnt1[a[i]][a[k]][j - i][k - j] = a[j];
				}
				else if(cnt1[a[i]][a[k]][j - i][k - j] != -2){
					if(cnt1[a[i]][a[k]][j - i][k - j] != a[j]){
						cnt1[a[i]][a[k]][j - i][k - j] = -2;
					}
				}
				//2
				if(cnt2[a[j]][a[k]][j - i][k - j] == -1){
					cnt2[a[j]][a[k]][j - i][k - j] = a[i];
				}
				else if(cnt2[a[j]][a[k]][j - i][k - j] != -2){
					if(cnt2[a[j]][a[k]][j - i][k - j] != a[j]){
						cnt2[a[j]][a[k]][j - i][k - j] = -2;
					}
				}
			}
		}
	}
	int num = (n + 39) / 40 + 1;
	int ok = 0;
	array<int, 5> ans = {(int)1e4, (int)1e4, (int)1e4, (int)1e4, (int)1e4};
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			for(int k = j + 1; k < n; k++){
				if(cnt[a[i]][a[j]][j - i][k - j].first >= 0 && cnt[a[i]][a[j]][j - i][k - j].second >= num){
					if(cnt1[a[i]][a[k]][j - i][k - j] >= 0 && cnt2[a[j]][a[k]][j - i][k - j] >= 0){
						ok = 1;
						if(j - i < ans[1]){
							ans = {a[i], j - i, a[j], k - j, a[k]};
						}
						else if(j - i == ans[1] && k - j < ans[3]){
							ans = {a[i], j - i, a[j], k - j, a[k]};
						}
					}
				}
			}
		}
	}
	if(!ok){
		cout << "random sequence\n";
		return 0;
	}
	cout << "triple correlation " << ans[0] << "(" << ans[1] << ")" << ans[2] << "(" << ans[3] << ")" << ans[4] << " found\n";
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 60ms
memory: 950860kb

input:

100
4 7 9 5 9 3 5 0 0 1 7 8 5 0 2 6 3 5 4 4
4 6 3 3 2 7 1 8 7 8 7 6 1 1 7 2 5 4 7 2
0 4 4 5 8 3 0 6 9 3 2 6 6 8 5 2 5 1 2 7
2 4 1 0 0 4 9 1 8 7 5 0 4 4 8 4 3 2 6 8
8 5 6 7 0 9 7 0 3 6 1 4 4 1 2 3 2 6 9 9

output:

triple correlation 4(1)4(3)3 found

result:

ok single line: 'triple correlation 4(1)4(3)3 found'

Test #2:

score: 0
Accepted
time: 40ms
memory: 950756kb

input:

10
1 2 3 1 2 2 1 1 3 0

output:

random sequence

result:

ok single line: 'random sequence'

Test #3:

score: 0
Accepted
time: 80ms
memory: 950700kb

input:

1
0

output:

random sequence

result:

ok single line: 'random sequence'

Test #4:

score: 0
Accepted
time: 83ms
memory: 950816kb

input:

2
0 1

output:

random sequence

result:

ok single line: 'random sequence'

Test #5:

score: -100
Wrong Answer
time: 55ms
memory: 951012kb

input:

30
8 7 4 2 5
2 5 7 2 5
8 2 3 2 3
5 4 9 5 9
6 1 6 1 1
4 1 0 5 0

output:

triple correlation 1(3)1(3)0 found

result:

wrong answer 1st lines differ - expected: 'triple correlation 8(3)2(15)5 found', found: 'triple correlation 1(3)1(3)0 found'