QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#287015#7963. 多折较差验证PYD1RE 0ms0kbC++143.2kb2023-12-19 11:57:232023-12-19 11:57:23

Judging History

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

  • [2023-12-19 11:57:23]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-12-19 11:57:23]
  • 提交

answer

#include <set>
#include <map>
#include <list>
#include <queue>
#include <cmath>
#include <time.h>
#include <random>
#include <bitset>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mk make_pair
#define fi first
#define se second

inline int read(){
	int t = 0,f = 1;
	register char c = getchar();
	while (c < 48 || c > 57) f = (c == '-') ? (-1) : (f),c = getchar();
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
	return f * t;
}

inline int reads(int *s){
	int t = 0;
	register char c = getchar();
	while (c != 'v' && c != '^') c = getchar();
	while (c == 'v' || c == '^') s[++t] = (c == 'v') ? 1 : -1,c = getchar();
	return t;
}

const int N = 100 + 10,INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int n,inp[N],to[N],recl[N],recr[N];

struct VAL{
	int v1;ll v2;
	VAL() {v1 = INF,v2 = LINF;}
	bool operator < (const VAL &rhs) const {return this->v1 != rhs.v1 ? this->v1 < rhs.v1 : this->v2 < rhs.v2;}
}dp[N][N];

struct Node{
	int l,r;VAL val;
	bool operator < (const Node &rhs) const {return this->val < rhs.val;}
}tmp[N];

bool check(int x,int y,int p){
	if (p < x || p > y) return 0;
    return p + to[p] > y || p - to[p] < x;
}

void upd(int l,int r,VAL v,int ad){
	++v.v1,v.v2 += ad;
	if (v < dp[l][r]) dp[l][r] = v;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif
	n = read();
    reads(inp);
    for (int i = 1;i <= n;i++){
        to[i] = n + 1;
        for (int j = 1;i - j >= 1 && i + j <= n;j++) if (inp[i - j] == inp[i + j]) {to[i] = j;break;}
    }
    for (int l = 1;l <= n;l++){
        for (int r = 0;r < l;r++) dp[l][r].v1 = dp[l][r].v2 = 0;
    }
	for (int i = 1;i <= n;i++) recl[i] = recr[i] = i,dp[i][i].v1 = 1,dp[i][i].v2 = 0;
    for (int len = 2;len <= n;len++){
        for (int l = 1,r = len;r <= n;l++,r++){
			// int dwn = r + r - l,up = min(n,to[r] + r + 1 - 1);
			// if (dwn > up) continue;
			// tmp[l] = (Node){dwn,up,dp[l][r]},++tmp[l].val.v1,tmp[l].val.v2 += r - l;
			int mid = (l + r) >> 1;
			if (check(l,r,mid)) recl[l] = mid;
			int p = recl[l];
			if (check(l,r,p)){
				if (p - l <= r - p) upd(l,r,dp[p + 1][r],l + r - 2 * p);
				if (r - p <= p - l) upd(l,r,dp[l][p - 1],2 * p - l - r);
			}
            // for (int p = l;p <= r;p++){
            //     if (check(l,r,p)){
            //         if (p - l <= r - p) upd(l,r,dp[p + 1][r],l + r - 2 * p);
            //         if (r - p <= p - l) upd(l,r,dp[l][p - 1],2 * p - l - r);
            //     }
            // }
        }
		for (int r = n,l = r - len + 1;l >= 1;l--,r--){
			int mid = (l + r + 1) >> 1;
			if (check(l,r,mid)) recr[r] = mid;
			int p = recr[r];
			if (check(l,r,p)){
				if (p - l <= r - p) upd(l,r,dp[p + 1][r],l + r - 2 * p);
				if (r - p <= p - l) upd(l,r,dp[l][p - 1],2 * p - l - r);
			}
		}
    }
    printf("%d %lld\n",dp[1][n].v1,dp[1][n].v2);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5000
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

output:


result: