QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#631787 | #515. A Random Problem | chuchu# | ML | 0ms | 0kb | C++14 | 2.8kb | 2024-10-12 10:17:31 | 2024-10-12 10:17:35 |
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