QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#432170#1282. Necklacechenxinyang2006WA 2ms9948kbC++204.9kb2024-06-06 21:11:512024-06-06 21:11:51

Judging History

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

  • [2024-06-06 21:11:51]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9948kb
  • [2024-06-06 21:11:51]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n;
int col[200005],a[200005],buc[200005];

int K;
pii b[200005];
vector <int> S[200005];
bool cmp(int x,int y){
	return a[x] < a[y];
}

int lst,fst;
void pick(int c){
	printf("%d ",S[c].back());
	S[c].pop_back();
	buc[c]--;
	lst = c;
	if(!fst) fst = c;
}

void constr(int idx,int sum){
	int j = 1;
	rep(i,1,sum){
		if(i % 2 == 0){
			while(!buc[j] || j == idx) j++; 
			pick(j);
		}else{
			pick(idx);
		}
	}
}

set <pii> SS;
void output(){
	printf("output\n");
	int sum = 0,idx = 0;
	rep(i,1,n){
		sum += buc[i];
		if(buc[i] > buc[idx]) idx = i;
	}
	assert(2 * buc[idx] <= sum);
/*	printf("output:\n");
	rep(i,1,n) printf("%d ",buc[i]);
	printf("\n");*/
	printf("%d\n",sum);
	if(2 * buc[idx] == sum){
		constr(idx,sum);
		printf("\n");
		return;
	}

	SS.clear();
	fst = lst = 0;
	rep(i,1,n) SS.insert(mkp(buc[i],i));
	pii cur;
	while(1){
		auto it = prev(SS.end());
		cur = *it;
		if(2 * cur.first == sum) break;

		if(cur.second == lst){
			it = prev(it);
			cur = *it;
		}
		pick(cur.second);
		sum--;
		SS.erase(it);
		if(cur.first > 1) SS.insert(mkp(cur.first - 1,cur.second));
	}
	assert(cur.second != lst);
	int ed = -1;
	for(pii I:SS) if(I.second != cur.second && I.second != fst) ed = I.second;

	assert(ed != -1);
	buc[ed]--;
	constr(cur.second,sum - 1);
	printf("%d ",S[ed].back());
	printf("\n");
}

ll dp[200005][6];
vector <int> solve(int lim,int m){
//	printf("solve %d %d\n",lim,m);
	rep(i,0,n){
		rep(k,0,m) dp[i][k] = -linf;
	}
	dp[0][0] = 0;

	ll sum;
	rep(i,1,n){
		sum = 0;
		rep(j,0,min(lim,SZ(S[i]))){
			if(j) sum += a[S[i][j - 1]];
			rep(k,0,m - j) chkmax(dp[i][j + k],dp[i - 1][k] + sum);
		}
	}
/*	rep(i,0,n){
		rep(j,0,m) printf("%lld ",dp[i][j]);
		printf("\n");
	}*/
	vector <int> res;
	if(dp[n][m] <= -1e15){
		res.eb(-1);
		return res;
	} 
	int cur = m,_j;
	per(i,n,1){
		sum = 0;
		_j = -1;
		rep(j,0,min(lim,SZ(S[i]))){
			if(j) sum += a[S[i][j - 1]];
			if(cur >= j && dp[i][cur] == dp[i - 1][cur - j] + sum) _j = j;
		}
		assert(_j != -1);
		rep(j,0,_j - 1) res.eb(S[i][j]);
		cur -= _j;
	}
	rep(k,0,SZ(res) - 2){
		if(col[res[k]] == col[res[k + 1]]){
			if(k) swap(res[k],res[k - 1]);
			else swap(res[k + 1],res[k + 2]);
		}
	}
	if(col[res[0]] == col[res.back()]) swap(res[0],res[1]);

	rep(k,0,SZ(res) - 2) assert(col[res[k]] != col[res[k + 1]]);
	assert(col[res[0]] != col[res.back()]);
	return res;
}

void solve(){
	scanf("%d",&n);
	rep(i,1,n) S[i].clear();
	fill(buc,buc + n + 1,0);
	rep(i,1,n) scanf("%d",&col[i]);
	rep(i,1,n) scanf("%d",&a[i]);
	rep(i,1,n) S[col[i]].eb(i);
	rep(i,1,n) sort(S[i].begin(),S[i].end(),cmp);

/*	printf("qwq\n");
	rep(i,1,n){
		for(int p:S[i]) printf("%d ",p);
		printf("\n");
	}*/
	ll answer = 0;
	int sum = 0;
	rep(i,1,n){
		if(a[i] > 0){
			answer += a[i];
			buc[col[i]]++;
			sum++;
		}
	}
	int m = 0;
	rep(i,1,n) if(buc[i] > buc[m]) m = i;
	if(2 * buc[m] > sum){
		K = 0;
		rep(i,1,n){
			if(col[i] == m){
				if(a[i] > 0) b[++K] = mkp(a[i],m);
			}else if(a[i] <= 0){
				b[++K] = mkp(-a[i],col[i]);
			}
		}
		sort(b + 1,b + K + 1);
	//	rep(i,1,K) printf("(%d,%d) ",b[i].first,b[i].second);
		int ext = 2 * buc[m] - sum;
		rep(i,1,ext){
			if(b[i].second == m){
				buc[m]--;
				sum--;
			}else{
				buc[b[i].second]++;
				sum++;
			}
		}
		return;
	}

	if(sum >= 3){
		output();
		return;
	}

	rep(i,1,n) reverse(S[i].begin(),S[i].end());
	vector <int> res1 = solve(1,3),res2 = solve(2,4);
/*	for(int p:res1) printf("%d ",p);
	printf("\n");
	for(int p:res2) printf("%d ",p);
	printf("\n");*/
	if(SZ(res1) == 1 && SZ(res2) == 1){
		printf("-1\n");
		return;
	}
	if(SZ(res1) == 1){
		swap(res1,res2);
	}else if(SZ(res2) > 1){
		ll awa = 0;
		for(int p:res1) awa += a[p];
		for(int p:res2) awa -= a[p];
		if(awa < 0) swap(res1,res2);
	}
	
	printf("%d\n",SZ(res1));
	for(int p:res1) printf("%d ",p);
	printf("\n");
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
4
1 1 1 1
1 2 3 4
4
1 1 2 2
1 2 3 4
8
2 6 5 4 3 1 7 7
-1 4 -1 2 10 -1 3 0
6
5 5 3 3 4 6
5 8 0 -1 -2 -7

output:

output
4
2 4 1 3 
output
4
7 2 4 5 

result:

wrong output format Expected integer, but "output" found