QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #395622 | #5529. Most Annoying Constructive Problem | Xun_xiaoyao | WA | 7ms | 3964kb | C++14 | 2.9kb | 2024-04-21 16:39:53 | 2024-04-21 16:39:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
int p[1010],num[1010],cnt,tot;
bool vis[1010];
int lgx[1010],rgx[1010];
void calc(int n,int k)
{
if(n<=5)
{
for(int i=1;i<=n;i++) p[i]=i;
do
{
tot=0;
for(int l=1;l<=n;l++)
{
for(int i=1;i<=n;i++) vis[i]=false;cnt=0;
for(int r=l;r<=n;r++)
{
for(int i=p[r]+1;i<=n;i++) if(vis[i]) cnt++;
if(cnt&1) tot++;
vis[p[r]]=true;
}
}
if(tot==k) return;
}while(next_permutation(p+1,p+n+1));
}
if(k==0)
{
for(int i=1;i<=n;i++) p[i]=i;
return;
}
if(k<n-1)
{
for(int i=1;i<=n;i++) p[i];
p[k]=k+2,p[k+1]=k,p[k+2]=k+1;
return;
}
if(k==n*(n-1)/2-(n-1)/2)
{
for(int i=1;i<=n;i+=2) num[i]=i+3;
for(int i=2;i<=n;i+=2) num[i]=i-1;
sort(num+1,num+n+1);
for(int i=1;i<=n;i+=2) p[i]=lower_bound(num+1,num+n+1,i+3)-num;
for(int i=2;i<=n;i+=2) p[i]=lower_bound(num+1,num+n+1,i-1)-num;
return;
}
if(k<=(n-2)*(n-3)/2-(n-3)/2+n-1)
{
p[n]=n-1,p[n-1]=n;
calc(n-2,k-(n-1));
return;
}
for(int i=2;i<n;i+=2) num[i]=i+2;
for(int i=3;i<n;i+=2) num[i]=i-2;
sort(num+2,num+n);
for(int i=2;i<n;i+=2) p[i]=lower_bound(num+2,num+n,i+2)-num-1;
for(int i=3;i<n;i+=2) p[i]=lower_bound(num+2,num+n,i-2)-num-1;
for(int i=1;i<n;i++)
{
lgx[i]=rgx[i]=0;
cnt=1;
for(int j=2;j<=n;j++)
{
if(i>p[j]) cnt++;
if((cnt+(n==2))&1) lgx[i]++;
}
cnt=1;
for(int j=n-1;j>1;j--)
{
if(i<=p[j]) cnt++;
if((cnt+(i==n-1)+((n&1)&&i==n-2))&1) rgx[i]++;
}
}
k-=(n-2)*(n-3)/2-(n-3)/2;
for(int l=1;l<n;l++)
for(int r=1;r<n;r++)
if(l<r)
{
if(k==lgx[l]+rgx[r]+((l-1+r-1+1)&1))
{p[1]=l,p[n]=r+1;break;}
}
else if(l>r)
{
if(k==lgx[l]+rgx[r]+((l-1+r-1)&1))
{p[1]=l+1,p[n]=r;break;}
}
else
{
if(k==lgx[l]+rgx[r]+((l-1+r-1+1)&1))
{p[1]=l,p[n]=r+1;break;}
if(k==lgx[l]+rgx[r]+((l-1+r-1)&1))
{p[1]=l+1,p[n]=r;break;}
}
if(p[1]<p[n])
{
for(int i=2;i<n;i++) if(p[i]>=p[1]) p[i]++;
for(int i=2;i<n;i++) if(p[i]>=p[n]) p[i]++;
}
else
{
for(int i=2;i<n;i++) if(p[i]>=p[n]) p[i]++;
for(int i=2;i<n;i++) if(p[i]>=p[1]) p[i]++;
}
}
int n,k;
void solve()
{
n=Qread(),k=Qread();
if(n<=5)
{
for(int i=1;i<=n;i++) p[i]=i;
do
{
tot=0;
for(int l=1;l<=n;l++)
{
for(int i=1;i<=n;i++) vis[i]=false;cnt=0;
for(int r=l;r<=n;r++)
{
for(int i=p[r]+1;i<=n;i++) if(vis[i]) cnt++;
if(cnt&1) tot++;
vis[p[r]]=true;
}
}
if(tot==k) break;
}while(next_permutation(p+1,p+n+1));
if(tot!=k) return printf("NO\n"),void();
}
else
{
if(k>n*(n-1)/2-(n-1)/2) return printf("NO\n"),void();
calc(n,k);
}
printf("YES\n");
for(int i=1;i<=n;i++) printf("%d ",p[i]);printf("\n");
}
int main()
{
int T=Qread();
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3964kb
input:
4 1 0 3 3 4 1 6 15
output:
YES 1 YES 3 2 1 YES 1 3 4 2 NO
result:
ok Correct (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 3800kb
input:
5951 27 255 28 371 31 320 33 201 32 199 31 108 15 78 27 32 24 268 20 4 14 82 29 202 33 85 26 104 31 380 27 330 20 140 29 192 21 63 17 89 20 41 32 444 20 76 27 114 33 330 26 249 33 301 24 87 25 72 14 49 25 281 21 58 15 48 16 19 14 0 22 175 11 7 30 43 31 259 22 112 12 30 30 111 33 268 30 287 19 150 15...
output:
YES 21 3 1 5 2 8 4 10 7 12 9 14 11 16 13 18 15 19 17 20 6 23 22 25 24 27 26 NO YES 20 3 1 5 2 7 4 9 6 11 8 13 10 15 12 17 14 19 16 21 18 23 22 25 24 27 26 29 28 31 30 YES 3 1 2 5 2 7 4 9 6 11 8 13 10 15 12 17 14 19 18 21 20 23 22 25 24 27 26 29 28 31 30 33 32 YES 3 1 2 5 2 7 9 7 8 11 8 13 10 15 1...
result:
wrong answer wrong number of odd subarrays (test case 1)