QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #432169 | #1282. Necklace | chenxinyang2006 | WA | 46ms | 9960kb | C++20 | 4.9kb | 2024-06-06 21:09:12 | 2024-06-06 21:09:13 |
Judging History
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(){
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){
output();
return;
}
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++;
}
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9960kb
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:
-1 4 2 4 1 3 4 7 2 4 5 4 3 2 4 1
result:
ok 4 cases.
Test #2:
score: -100
Wrong Answer
time: 46ms
memory: 9872kb
input:
36398 6 4 6 4 4 5 2 7 -9 -9 4 -1 -8 2 1 1 -8 -5 2 2 1 10 7 9 5 6 5 8 2 3 3 7 8 -7 5 -5 7 8 7 -5 -5 8 2 1 2 6 -8 9 2 3 3 5 3 9 3 9 3 5 2 -2 5 -8 -5 -3 6 -2 4 4 2 4 1 -1 -1 10 -4 4 3 1 2 1 -9 -6 4 10 5 4 3 4 1 4 -8 1 6 10 -8 6 2 6 3 5 4 1 1 -7 4 0 6 -6 6 6 6 5 2 1 2 3 1 2 -8 -7 0 10 2 9 10 7 8 7 6 7 6...
output:
4 1 5 4 6 0 2 2 1 5 9 2 4 6 5 -1 4 8 4 2 1 3 3 2 4 2 4 3 3 3 2 4 3 5 3 1 4 1 6 2 3 5 6 7 4 9 10 4 2 9 6 3 6 3 4 2 7 8 6 5 2 6 3 1 9 0 6 5 2 3 1 8 6 2 4 1 3 2 1 4 -1 4 3 2 5 1 -1 4 7 2 8 3 4 3 5 2 7 -1 5 2 6 4 8 7 4 6 5 2 4 0 5 3 7 4 1 5 4 5 6 8 2 0 4 3 1 2 4 0 4 1 2 6 5 ...
result:
wrong answer case #2: expected -1 or [3, 2]