QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #638589 | #4929. Longest Unfriendly Subsequence | jinzikai314 | 0 | 36ms | 7956kb | C++14 | 2.1kb | 2024-10-13 16:18:49 | 2024-10-13 16:18:50 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define int ll
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mid (l+r>>1)
#define rg register
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define prq_mn(x) priority_queue<x, vector<x>, greater<x> >
#define prq_mx(x) priority_queue<x, vector<x>, less<x> >
#define fi first
#define se second
#define DEBUG printf("Debug on line %d\n", __LINE__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 5e2 + 5;
const int INF = 0x3f3f3f3f;
template <typename T> bool updmax(T& a, T b) {return a<b ? a=b, 1 : 0;}
template <typename T> bool updmin(T& a, T b) {return a>b ? a=b, 1 : 0;}
inline int read(){
int n=0, f=1; char ch = getchar();
for(; !isdigit(ch); ch=getchar()) if(ch == '-') f=-1;
for(; isdigit(ch); ch=getchar()) n=n*10+ch-'0';
return n*f;
}
int T;
int n, m;
int a[N];
vector<int> vec;
int f[2][N][N];
signed main(){
T = read();
while(T--){
vec.clear();
n = read();
for(int i=1; i<=n; i++){
a[i] = read();
vec.pb(a[i]);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
m = vec.size();
for(int i=1; i<=n; i++){
a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
// printf("a[%d] = %d\n", i, a[i]);
}
memset(f, -INF, sizeof f);
f[0][0][0] = 0;
for(int ii=1; ii<=n; ii++){
int i=ii&1, lst = (ii-1)&1;
for(int j=0; j<=m; j++){
for(int k=0; k<=m; k++){
f[i][j][k] = max(f[i][j][k], f[lst][j][k]);
if(a[ii]!=j && a[ii]!=k) f[i][a[ii]][j] = max(f[i][a[ii]][j], f[lst][j][k] + 1);
}
}
memset(f[lst], -INF, sizeof f[lst]);
for(int j=0; j<=m; j++){
for(int k=0; k<=m; k++){
printf("f[%d][%d][%d] = %d\n", ii, j, k, f[i][j][k]);
}
printf("\n");
}
}
int ans = -INF;
for(int j=0; j<=m; j++){
for(int k=0; k<=m; k++){
ans = max(ans, f[n&1][j][k]);
}
}
printf("%lld\n", ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
1 200000 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 2...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 3ms
memory: 7748kb
input:
3 5 1 2 1 2 1 7 1 2 3 2 1 2 3 8 1 10 10 1 1 100 100 1
output:
f[1][0][0] = 0 f[1][0][1] = -1044266559 f[1][0][2] = -1044266559 f[1][1][0] = 1 f[1][1][1] = -1044266559 f[1][1][2] = -1044266558 f[1][2][0] = -1044266559 f[1][2][1] = -1044266559 f[1][2][2] = -1044266559 f[2][0][0] = 0 f[2][0][1] = -1044266559 f[2][0][2] = -1044266559 f[2][1][0] = 1 f[2][1][1] ...
result:
wrong answer 1st lines differ - expected: '2', found: 'f[1][0][0] = 0'
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 36ms
memory: 7836kb
input:
1 500 537076440 691668159 871942500 537076440 537076440 691668159 871942500 871942500 537076440 691668159 871942500 537076440 691668159 871942500 537076440 691668159 871942500 537076440 691668159 871942500 537076440 691668159 871942500 871942500 537076440 691668159 871942500 537076440 537076440 6916...
output:
f[1][0][0] = 0 f[1][0][1] = -1044266559 f[1][0][2] = -1044266559 f[1][0][3] = -1044266559 f[1][1][0] = 1 f[1][1][1] = -1044266559 f[1][1][2] = -1044266558 f[1][1][3] = -1044266558 f[1][2][0] = -1044266559 f[1][2][1] = -1044266559 f[1][2][2] = -1044266559 f[1][2][3] = -1044266559 f[1][3][0] = -104...
result:
wrong answer 1st lines differ - expected: '361', found: 'f[1][0][0] = 0'
Subtask #4:
score: 0
Wrong Answer
Test #79:
score: 0
Wrong Answer
time: 0ms
memory: 7956kb
input:
1 200000 1 3 3 2 2 3 3 1 2 3 1 1 3 3 3 2 1 1 2 3 2 1 3 3 3 1 2 2 1 3 1 2 1 2 3 2 3 3 2 2 3 2 3 2 3 1 1 1 1 1 3 1 3 2 3 3 3 3 1 3 2 1 3 2 3 2 3 1 1 1 1 3 3 2 3 2 1 2 2 3 2 3 2 2 2 2 2 2 3 2 1 2 2 1 1 3 2 1 2 1 1 3 3 3 2 1 2 2 2 1 3 3 2 3 2 1 3 3 2 2 1 3 1 3 2 1 2 3 2 1 2 3 2 2 3 2 1 2 1 1 1 1 1 1 1 3...
output:
f[1][0][0] = 0 f[1][0][1] = -1044266559 f[1][0][2] = -1044266559 f[1][0][3] = -1044266559 f[1][1][0] = 1 f[1][1][1] = -1044266559 f[1][1][2] = -1044266558 f[1][1][3] = -1044266558 f[1][2][0] = -1044266559 f[1][2][1] = -1044266559 f[1][2][2] = -1044266559 f[1][2][3] = -1044266559 f[1][3][0] = -104...
result:
wrong answer 1st lines differ - expected: '66691', found: 'f[1][0][0] = 0'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #3:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%