Task: | Grid |
Sender: | ainta1 |
Submission time: | 2017-01-22 09:07:37 +0200 |
Language: | C++ |
Status: | READY |
Result: | 65 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | ACCEPTED | 21 |
#3 | ACCEPTED | 44 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.04 s | 1 | details |
#2 | ACCEPTED | 0.04 s | 1 | details |
#3 | ACCEPTED | 0.04 s | 1 | details |
#4 | ACCEPTED | 0.03 s | 1 | details |
#5 | ACCEPTED | 0.05 s | 1 | details |
#6 | ACCEPTED | 0.04 s | 1 | details |
#7 | ACCEPTED | 0.04 s | 1 | details |
#8 | TIME LIMIT EXCEEDED | -- | 1 | details |
#9 | ACCEPTED | 0.04 s | 1 | details |
#10 | ACCEPTED | 0.04 s | 2 | details |
#11 | ACCEPTED | 0.05 s | 2 | details |
#12 | ACCEPTED | 0.03 s | 2 | details |
#13 | ACCEPTED | 0.03 s | 2 | details |
#14 | ACCEPTED | 0.04 s | 2 | details |
#15 | ACCEPTED | 0.05 s | 2 | details |
#16 | ACCEPTED | 0.04 s | 3 | details |
#17 | ACCEPTED | 0.02 s | 3 | details |
#18 | ACCEPTED | 0.03 s | 3 | details |
#19 | ACCEPTED | 0.06 s | 3 | details |
#20 | ACCEPTED | 0.12 s | 3 | details |
#21 | ACCEPTED | 0.12 s | 3 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:403:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&K); ^
Code
/*#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int n, m, RR[40][40], DD[40][40], ES[40][40]; long long res; int Num(int x, int y, int ck){ return (x-1)*m+y + ck*n*m; } struct Edge{ int b, e, c, f; }E[201000]; int EC, source, sink; vector<int>G[5000]; void Make_Edge(int b, int e, int f, int c){ G[b].push_back(EC);G[e].push_back(EC+1); E[EC].b=b,E[EC].e=e,E[EC].f=f,E[EC].c=c;EC++; E[EC].b=e,E[EC].e=b,E[EC].f=0,E[EC].c=-c;EC++; } int Path[10100], D[10100], Q[1010000], InQ[10100]; int SPFA(){ int i, head = 0, tail = 0, x; for(i=0;i<=sink;i++){ D[i] = -1e9; InQ[i] = 0; } D[0] = 0; Q[++tail] = 0; InQ[0] = 1; while(head < tail){ x = Q[++head]; InQ[x] = 0; for(i=0;i<G[x].size();i++){ Edge tp = E[G[x][i]]; if(tp.f && D[tp.e] < D[x] + tp.c){ D[tp.e] = D[x] + tp.c; Path[tp.e] = G[x][i]; if(!InQ[tp.e]){ InQ[tp.e] = 1; Q[++tail] = tp.e; } } } } return D[sink]; } void MCMF(){ int t, x, y, f; while((t = SPFA()) >= 0){ x = sink; f = 100; while(x){ y = Path[x]; f=min(f,E[y].f); x = E[y].b; } res += 1ll*f*t; x = sink; while(x){ y = Path[x]; E[y].f -= f; E[y^1].f += f; x = E[y].b; } } } int main(){ int TC,TT,i,j,K; scanf("%d",&TC); for(TT=1;TT<=TC;TT++){ printf("Case #%d: ",TT); scanf("%d%d",&n,&m); for(i=1;i<=n;i++)for(j=1;j<m;j++)scanf("%d",&RR[i][j]); for(i=1;i<n;i++)for(j=1;j<=m;j++)scanf("%d",&DD[i][j]); EC = 0; source = 0, sink = n*m*2+1; scanf("%d",&K); for(i=1;i<=K;i++){ int x,y; scanf("%d%d",&x,&y); ES[x][y]=1; } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ } } MCMF(); if(res < -5000000){ printf("Impossible\n"); } else{ printf("%lld\n",res); } for(i=0;i<=sink;i++){ G[i].clear(); } } }*/ /* #include<stdio.h> #include<algorithm> #include<cstdlib> using namespace std; int n, K, w[1010000]; long long res, S[1010000], Sum, D1[1010000][8], D2[1010000][8], D[64][2], DP[2048][2]; bool v[64][2]; int C[2048], M[2048], m, Path[2048][2]; bool vv[2048][2]; void Dijk(){ int i, j; for(i=0;i<(1<<m);i++)v[i][0]=v[i][1]=false; while(1){ int x=-1, y=-1; long long MM = 1e17; for(i=0;i<(1<<m);i++){ for(j=0;j<2;j++){ if(MM > D[i][j] && !v[i][j]){ MM = D[i][j]; x=i,y=j; } } } if(x==-1)break; v[x][y]=true; if(y==0){ for(j=0;j<(1<<m);j++){ if(j&x || C[j]>3)continue; D[x^j][1] = min(D[x^j][1], D[x][y] + M[j]); } } else{ for(j=0;j<m;j++){ if(!((1<<j)&x))continue; D[x^(1<<j)][0] = min(D[x^(1<<j)][0], D[x][y] + w[j+1]); } } } } void Dijk2(){ int i, j; for(i=0;i<(1<<n);i++)vv[i][0]=vv[i][1]=false; while(1){ int x=-1, y=-1; long long MM = 1e17; for(i=0;i<(1<<n);i++){ for(j=0;j<2;j++){ if(MM > DP[i][j] && !vv[i][j]){ MM = DP[i][j]; x=i,y=j; } } } if(x==-1)break; vv[x][y]=true; if(y==0){ for(j=0;j<(1<<n);j++){ if(j&x || C[j]>3)continue; if(DP[x^j][1] > DP[x][y] + M[j]) Path[x^j][1] = x; DP[x^j][1] = min(DP[x^j][1], DP[x][y] + M[j]); } } else{ for(j=0;j<n;j++){ if(!((1<<j)&x))continue; if(DP[x^(1<<j)][0]> DP[x][y] + w[j+1]) Path[x^(1<<j)][0] = x; DP[x^(1<<j)][0] = min(DP[x^(1<<j)][0], DP[x][y] + w[j+1]); } } } } int TP[1010]; long long Do(int a, int b, int c){ int t = a*3-a-b-c, i; long long S = 1ll*a*w[1]+1ll*b*w[2]+1ll*c*w[3]; for(i=n;i>=6;i-=3){ if(i-3 >= 3+t){ S += w[i]; } else break; } int ed = i; for(i=ed;i>=4;i--)TP[i] = 1; TP[1]=a+1,TP[2]=b+1,TP[3]=c+1; int s = ed+a+b+c; if(s%3==2){ TP[1]--,TP[2]--; S+=w[2]; } while(1){ int x1=-1,x2=-1,x3=-1; for(i=1;i<=n;i++){ if(TP[i]){ if(x1==-1)x1=i; else if(x2==-1)x2=i; else if(x3==-1){ x3=i; break; } } } if(x1==-1)break; TP[x1]--,TP[x2]--,TP[x3]--; S += w[x3]; } return S; } int main(){ int i, j, k; srand(1879); int tc=0; while(1){ printf("%d\n",++tc); n = 9, K = 3; for(i=1;i<=n;i++){ w[i] = rand()%5+1; } sort(w+1,w+n+1); for(i=0;i<=n;i++){ for(j=0;j<8;j++){ D1[i][j]=D2[i][j]=1e18; } } for(i=0;i<(1<<n);i++){ C[i] = 0, M[i] = 0; } m = min(n,6); for(i=0;i<(1<<n);i++){ for(j=0;j<n;j++)if(i&(1<<j))C[i]++, M[i] = w[j+1]; } D1[n][0] = 0; res = 1e18; for(i=n;i>=6;i--){ for(int cc = 0; cc <= 4; cc++){ for(j=0;j<8;j++){ if(C[j] != cc)continue; if(D2[i][j]>1e17)continue; for(k=0;k<3;k++){ if((1<<k)&j){ D1[i][j^(1<<k)] = min(D1[i][j^(1<<k)], D2[i][j] + w[k+1]); } } } for(j=0;j<8;j++){ if(C[j] != cc-1)continue; for(k=0;k<8;k++){ if(k&j)continue; if(C[k]>=2)D2[i][j^k] = min(D2[i][j^k], D1[i][j] + M[k]); if(C[k]==3)continue; D2[i-1][j^k] = min(D2[i-1][j^k], D1[i][j] + w[i]); if(C[k]==2)continue; D2[i-2][j^k] = min(D2[i-2][j^k], D1[i][j] + w[i]); if(C[k]==1)continue; D2[i-3][j^k] = min(D2[i-3][j^k], D1[i][j] + w[i]); } } } } for(i=0;i<(1<<m);i++)D[i][0]=D[i][1]=1e18; for(i=3;i<=m;i++){ for(j=0;j<8;j++){ int s = 0; for(k=0;k<m;k++){ if(k>=i || (k<3 && j&(1<<k))) s += (1<<k); } D[s][0] = D1[i][j]; D[s][1] = D2[i][j]; } } Dijk(); long long res1 = D[(1<<m)-1][1]; int ret = (n-2)/2; res1 = 1e18; for(i=0;i<=ret;i++){ for(j=0;i+j<=ret;j++){ k=ret-i-j; if(i<j||j<k)continue; res1 = min(res1,Do(i,j,k)); } } for(i=0;i<(1<<n);i++)DP[i][0]=DP[i][1]=1e18; DP[0][0] = 0; Dijk2(); long long res2 = DP[(1<<n)-1][1]; if(res1 != res2){ for(i=1;i<=n;i++)printf("%d ",w[i]); printf("\n"); printf("%lld %lld\n",res1,res2); int x = (1<<n)-1, y = 1; while(x||y){ printf("%d %d\n",x,y); x = Path[x][y]; y = !y; } break; } } }*/ /* #include<stdio.h> #include<algorithm> using namespace std; int n, K; int w[1010000], TP[1010000]; long long S[1010000], res; void Do(int a, int b, int c){ int t = a*3-a-b-c, i; long long S = 1ll*a*w[1]+1ll*b*w[2]+1ll*c*w[3]; for(i=n;i>=6;i-=3){ if(i-3 >= 3+t){ S += w[i]; } else break; } int ed = i; for(i=ed;i>=4;i--)TP[i] = 1; TP[1]=a+1,TP[2]=b+1,TP[3]=c+1; int s = ed+a+b+c; if(s%3==2){ TP[1]--,TP[2]--; S+=w[2]; } while(1){ int x1=-1,x2=-1,x3=-1; for(i=1;i<=n;i++){ if(TP[i]){ if(x1==-1)x1=i; else if(x2==-1)x2=i; else if(x3==-1){ x3=i; break; } } } if(x1==-1)break; TP[x1]--,TP[x2]--,TP[x3]--; S += w[x3]; } res = min(res,S); } int main(){ int i, j, k; scanf("%d%d",&n,&K); for(i=1;i<=n;i++){ scanf("%d",&w[i]); S[i] = S[i-1] + w[i]; } if(n<=K){ printf("%d\n",w[n]); return 0; } if(K==2){ long long Sum; Sum = S[n]-S[1] + 1ll*w[1]*(n-2); res = Sum; for(i=n-1;i>=3;i-=2){ Sum -= w[i]+w[i+1]+w[1]*2; Sum += w[i+1]+w[2]+w[2]+w[1]; res = min(res,Sum); } printf("%lld\n",res); return 0; } if(n>100)return 0; int ret = (n-2)/2; res = 1e18; for(i=0;i<=ret;i++){ for(j=0;i+j<=ret;j++){ k=ret-i-j; if(i<j||j<k)continue; Do(i,j,k); } } printf("%lld\n",res); }*/ #include<stdio.h> #include<algorithm> using namespace std; int X[1010],Y[1010], n, BE = 6, K; int w[1010][1010]; struct point{ int c, pv; bool operator<(const point &p)const{ return c<p.c; } }P[2010]; void Ins(int x, int y, int c){ w[x][y] = c; X[x] += c; Y[y] += c; } int main(){ int i, j; scanf("%d",&K); if(K==9){ while(1){} } if(K<=3){ printf("QAQ\n"); return 0; } if(K==4){ printf("1 1 2 2\n1 2 3 3\n1 2 3 4\n4 3 4 4\n"); return 0; } if(K==5){ printf("2 3 1 1 1\n1 5 5 3 3\n2 3 5 2 4\n5 4 5 4 1\n2 3 4 4 2\n"); return 0; } BE = (K-2)/4*4+2; for(i=1;i<=BE;i++){ for(j=1;j<=BE;j++){ if(i!=j)Ins(i,j,i); else Ins(i,j,BE+1-j); } } for(n=BE;n<K;n++){ for(i=1;i<=n;i++){ P[i].c = X[i],P[i].pv=i; P[i+n].c = Y[i],P[i+n].pv=n+i; } sort(P+1,P+n*2+1); for(i=1;i<n*2;i++){ if(P[i].c==P[i+1].c){ printf("%d\n",n); while(1){} } } for(i=1;i<=n;i++){ if(P[i].pv <= n){ Ins(P[i].pv,n+1,i); w[P[i].pv][n+1] = i; } else{ Ins(n+1,P[i].pv-n,i); } } for(i=1;i<=n+1;i++){ if(!w[n+1][i])Ins(n+1,i,n+1); if(!w[i][n+1])Ins(i,n+1,n+1); } } for(i=1;i<=K;i++){ for(j=1;j<=K;j++)printf("%d ",w[i][j]); printf("\n"); } }
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
2 |
correct output |
---|
QAQ |
user output |
---|
QAQ |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
3 |
correct output |
---|
QAQ |
user output |
---|
QAQ |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
4 |
correct output |
---|
3 4 3 4 3 1 1 2 4 4 3 2 2 2 1 1 |
user output |
---|
1 1 2 2 1 2 3 3 1 2 3 4 4 3 4 4 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
5 |
correct output |
---|
2 3 4 1 1 3 4 2 1 2 4 2 3 1 3 4 3 2 1 4 5 5 5 5 5 |
user output |
---|
2 3 1 1 1 1 5 5 3 3 2 3 5 2 4 5 4 5 4 1 2 3 4 4 2 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
6 |
correct output |
---|
2 3 4 5 1 1 3 4 5 2 1 2 4 5 2 3 1 3 5 2 3 4 1 4 5 4 3 2 1 5 ... |
user output |
---|
6 1 1 1 1 1 2 5 2 2 2 2 3 3 4 3 3 3 4 4 4 3 4 4 5 5 5 5 2 5 ... |
Test 6
Group: 1
Verdict: ACCEPTED
input |
---|
7 |
correct output |
---|
2 3 4 5 6 1 1 3 4 5 6 2 1 2 4 5 6 2 3 1 3 5 6 2 3 4 1 4 6 2 3 4 5 1 5 ... |
user output |
---|
6 1 1 1 1 1 1 2 5 2 2 2 2 2 3 3 4 3 3 3 5 4 4 4 3 4 4 7 5 5 5 5 2 5 7 ... |
Test 7
Group: 1
Verdict: ACCEPTED
input |
---|
8 |
correct output |
---|
2 3 4 5 6 7 1 1 3 4 5 6 7 2 1 2 4 5 6 7 2 3 1 3 5 6 7 2 3 4 1 4 6 7 2 3 4 5 1 5 ... |
user output |
---|
6 1 1 1 1 1 1 1 2 5 2 2 2 2 2 2 3 3 4 3 3 3 5 5 4 4 4 3 4 4 7 8 5 5 5 5 2 5 7 8 ... |
Test 8
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
9 |
correct output |
---|
2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 2 1 2 4 5 6 7 8 2 3 1 3 5 6 7 8 2 3 4 1 4 6 7 8 2 3 4 5 1 5 ... |
user output |
---|
(empty) |
Test 9
Group: 1
Verdict: ACCEPTED
input |
---|
10 |
correct output |
---|
2 3 4 5 6 7 8 9 1 1 3 4 5 6 7 8 9 2 1 2 4 5 6 7 8 9 2 3 1 3 5 6 7 8 9 2 3 4 1 4 6 7 8 9 2 3 4 5 1 5 ... |
user output |
---|
10 1 1 1 1 1 1 1 1 1 2 9 2 2 2 2 2 2 2 2 3 3 8 3 3 3 3 3 3 3 4 4 4 7 4 4 4 4 4 4 5 5 5 5 6 5 5 5 5 5 ... |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
3 |
correct output |
---|
QAQ |
user output |
---|
QAQ |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
4 |
correct output |
---|
3 4 3 4 3 1 1 2 4 4 3 2 2 2 1 1 |
user output |
---|
1 1 2 2 1 2 3 3 1 2 3 4 4 3 4 4 |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
29 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
26 1 1 1 1 1 1 1 1 1 1 1 1 1 1... |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
48 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
46 1 1 1 1 1 1 1 1 1 1 1 1 1 1... |
Test 14
Group: 2
Verdict: ACCEPTED
input |
---|
80 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
78 1 1 1 1 1 1 1 1 1 1 1 1 1 1... |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
97 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
94 1 1 1 1 1 1 1 1 1 1 1 1 1 1... |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
3 |
correct output |
---|
QAQ |
user output |
---|
QAQ |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
4 |
correct output |
---|
3 4 3 4 3 1 1 2 4 4 3 2 2 2 1 1 |
user output |
---|
1 1 2 2 1 2 3 3 1 2 3 4 4 3 4 4 |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
111 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
110 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
506 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
506 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
844 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
842 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
991 |
correct output |
---|
2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
990 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |