QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #605542 | #8940. Piggy Sort | qiuuu | WA | 1ms | 4184kb | C++14 | 1.4kb | 2024-10-02 17:51:05 | 2024-10-02 17:51:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=509;
int n,m,t,sum[N];
int a[N][N],ans[N];
bool vis[N][N];
pair<int,int> su[N];
int main()
{
scanf("%d",&t);
while(t--)
{
memset(vis,0,sizeof(vis));
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int j=1;j<=n;j++)
sum[i]+=a[i][j];
}
if(m==1||sum[1]==sum[2])
{
for(int i=1;i<=n;i++) printf("%d ",i);
puts("");
continue;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(vis[2][j]) continue;
long long x=a[2][j]-a[1][i],v=a[2][j];
if(x<0) continue;
int y=sum[2]-sum[1];
int fg=0;
for(int k=3;k<=m;k++)
{
if(x*(sum[k]-sum[k-1])%y) break;
long long u=x*(sum[k]-sum[k-1])/y;
v+=u;
int uu=lower_bound(a[k]+1,a[k]+n+1,v)-a[k];
int vv=upper_bound(a[k]+1,a[k]+n+1,v)-a[k];
bool flg=0;
for(int j=uu;j<vv;j++)
{
if(!vis[k][j])
{
vis[k][j]=1;
flg=1;
break;
}
}
if(!flg) break;
if(k==m) fg=1;
}
if(fg==1)
{
su[i]=make_pair(x,i);
break;
}
}
}
sort(su+1,su+n+1);
for(int i=1;i<=n;i++) ans[su[i].second]=i;
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
puts("");
}
}
/*
3
2 4
1 2
3 4
5 6
7 8
1 2
1
1
3 4
1 2 3
6 9 9
10 15 17
12 18 21
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4080kb
input:
3 2 4 1 2 3 4 5 6 7 8 1 2 1 1 3 4 1 2 3 6 9 9 10 15 17 12 18 21
output:
1 2 1 3 1 2
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4184kb
input:
41 1 2 -19 9531 2 3 11 13 3175 4759 2211 3313 10 19 -54 -25 -19 -18 -1 3 61 63 85 88 -54 753 863 2397 3111 4649 4671 4756 5507 7762 -54 369 479 1245 1575 2345 2367 2452 2819 3922 -54 553 663 1797 2311 3449 3471 3556 4107 5762 -54 87 197 399 447 653 675 760 845 1102 -54 320 430 1098 1379 2051 2073 21...
output:
0 1 2 1 2 6 10 5 7 9 4 3 8 8 7 5 9 2 1 6 3 4 1 6 5 9 8 2 3 10 4 7 3 5 10 6 7 4 9 8 2 1 4 3 1 8 2 5 6 7 3 1 5 2 6 9 8 7 4 10 2 3 1 4 3 2 9 1 4 6 7 5 8 1 5 2 6 7 3 4 8 9 9 8 5 7 2 3 4 6 1 1 2 4 8 5 7 10 6 9 3 7 1 3 2 9 8 10 4 5 6 7 8 1 2 5 6 3 9 4 8 1 2 7 6 9 3 5 4 8 1 2 4 5 10 9 3 6 7...
result:
wrong answer 1st lines differ - expected: '1', found: '0 '