QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631787#515. A Random Problemchuchu#ML 0ms0kbC++142.8kb2024-10-12 10:17:312024-10-12 10:17:35

Judging History

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

  • [2024-10-12 10:17:35]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-12 10:17:31]
  • 提交

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];
pair<int, int> cnt1[11][11][1001][1001];
pair<int, 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].first = -1;
					cnt1[i][j][k][l].second = -1;
					cnt2[i][j][k][l].first = -1;
					cnt2[i][j][k][l].second = -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].first == -1){
					cnt1[a[i]][a[k]][j - i][k - j].first = a[j];
					cnt1[a[i]][a[k]][j - i][k - j].second = 1;
				}
				else if(cnt1[a[i]][a[k]][j - i][k - j].first != -2){
					if(cnt1[a[i]][a[k]][j - i][k - j].first != a[j]){
						cnt1[a[i]][a[k]][j - i][k - j].first = -2;
					}
					cnt1[a[i]][a[k]][j - i][k - j].second++;
				}
				//2
				if(cnt2[a[j]][a[k]][j - i][k - j].first == -1){
					cnt2[a[j]][a[k]][j - i][k - j].first = a[i];
					cnt2[a[j]][a[k]][j - i][k - j].second = 1;
				}
				else if(cnt2[a[j]][a[k]][j - i][k - j].first != -2){
					if(cnt2[a[j]][a[k]][j - i][k - j].first != a[j]){
						cnt2[a[j]][a[k]][j - i][k - j].first = -2;
					}
					cnt2[a[j]][a[k]][j - i][k - j].second++;
				}
			}
		}
	}
	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].first >= 0 && cnt2[a[j]][a[k]][j - i][k - j].first >= 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: 0
Memory Limit Exceeded

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: