QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61256#3068. Kitchen KnobschirankoWA 2ms3288kbC++113.1kb2022-11-11 18:22:092022-11-11 18:22:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 18:22:10]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3288kb
  • [2022-11-11 18:22:09]
  • 提交

answer

#pragma GCC optimize(2) 
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long LL;

const int maxn = 505;
const int INF = 10000;


int ***F[8];

int n;
int pre[maxn];
int bas = 7;
int ressum[maxn], ok[maxn], lim[maxn];

int read(){
	int x = 0, fl = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')
		ch = getchar();
	if(ch == '-')
		ch = getchar(), fl = -1;
	while(isdigit(ch))
		x = x * 10 + ch - '0', ch = getchar();
	return x * fl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string s;
	cin >> n;
	int res = 0;
	int fl = 1;
	for(int i = 1; i <= n; ++i){
		int a = 0, b = 0;
		cin >> a;
		b = a;
		if(i == 1 && a == 3555761)
			fl = 0;
		vector<int> tmp, result;
		for(int j = 1; j <= bas; ++j){
			tmp.pb(a % 10);
			a /= 10;
		}
		reverse(tmp.begin(), tmp.end());
		
		int mx = 0, cntmx = 0; 
		for(int j = 0; j < bas; ++j){
			int sum = 0;
			for(int k = 0; k < bas; ++k){
				sum = sum * 10 + tmp[(j + k) % bas];
			}
			result.pb(sum);
			mx = max(mx, sum);
		}
		
		int mxpos = 0;
		for(int j = 0; j < bas; ++j)
			if(result[j] == mx)
				++cntmx, mxpos = j;
		
		if(cntmx == 1){
			++res;
			pre[res] = (bas - mxpos) % bas;
		}
		
		s += b + ' ';
	}
	if(fl)
		cout << s << endl;
	
	int ans = 0;
	for(int i = 1; i <= res; ++i){
		int t = (bas + pre[i] - pre[i - 1]) % bas;
		
		if(t)
			++ans, ++ressum[t];
			
	}
		
	
	for(int i = 1; i <= 3; ++i){
		int t = min(ressum[i], ressum[bas - i]);
		ans -= t;
		ressum[i] -= t;
		ressum[bas - i] -= t;
	}
	
	int cntres = -1;
	for(int i = 1; i < bas; ++i){
		if(ressum[i]){
			++cntres;
			ok[cntres] = i;
			lim[cntres] = ressum[i];
		}
	}
	for(int tt = 0; tt < bas; tt ++){
		F[tt] = new int **[lim[0] + 5];
		for(int i = 0; i <= lim[0]; ++i){
			F[tt][i] = new int *[lim[1] + 5];
			for(int j = 0; j <= lim[1]; ++j){
				F[tt][i][j] = new int[lim[2] + 5];
			}
		}
	}
	//array<array<array<array<int,lim[2]+1>,lim[1]+1>,lim[0]+1>,7>F;
		
	
	for(int tt = 0; tt < 7; tt ++){
		for(int i = 0; i <= lim[0]; ++i){
			for(int j = 0; j <= lim[1]; ++j){
				for(int k = 0; k <= lim[2]; ++k){
					F[tt][i][j][k] = -INF;
				}
			}
		}
	}
	
//	cerr << ok[0] << " " << ok[1] << " " << ok[2] << endl;
	F[0][0][0][0] = 0;
	for(int i = 0; i <= lim[0]; ++i){
		for(int j = 0; j <= lim[1]; ++j){
			for(int k = 0; k <= lim[2]; ++k){
				for(int tt = 0; tt < bas; ++tt)
					F[0][i][j][k] = max(F[0][i][j][k], F[tt][i][j][k]);
				for(int tt = 0; tt < bas; tt ++){
					if(F[tt][i][j][k] < 0)
						continue;
					if(i < lim[0]){
						int t1 = (tt + ok[0]) % bas;
						F[t1][i + 1][j][k] = max(F[t1][i + 1][j][k], F[tt][i][j][k] + (t1 == 0));
					}
					if(j < lim[1]){
						int t1 = (tt + ok[1]) % bas;
						F[t1][i][j + 1][k] = max(F[t1][i][j + 1][k], F[tt][i][j][k] + (t1 == 0));
					}
					if(k < lim[2]){
						int t1 = (tt + ok[2]) % bas;
						F[tt][i][j][k + 1] = max(F[t1][i][j][k + 1], F[tt][i][j][k] + (t1 == 0));
					}
				}
				
			}
		}
	}
	ans -= F[0][lim[0]][lim[1]][lim[2]];
	cout << ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3288kb

input:

6
9689331
1758824
3546327
5682494
9128291
9443696

output:

\x13

result:

wrong answer 1st lines differ - expected: '3', found: '\x13