— Dark mode

Datatähti Open 2017

Grid

  • Start: N/A
  • End: N/A
CSES - Datatähti Open 2017 - Results
Submission details
Task:Grid
Sender:ainta1
Submission time:2017-01-22 09:28:39 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED35
#2ACCEPTED21
#3ACCEPTED44
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.04 s1details
#3ACCEPTED0.04 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.04 s1details
#8ACCEPTED0.02 s1details
#9ACCEPTED0.04 s1details
#10ACCEPTED0.04 s2details
#11ACCEPTED0.04 s2details
#12ACCEPTED0.04 s2details
#13ACCEPTED0.05 s2details
#14ACCEPTED0.04 s2details
#15ACCEPTED0.04 s2details
#16ACCEPTED0.04 s3details
#17ACCEPTED0.05 s3details
#18ACCEPTED0.03 s3details
#19ACCEPTED0.07 s3details
#20ACCEPTED0.11 s3details
#21ACCEPTED0.12 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:405: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>
#include<cstdlib>
using namespace std;
int X[1010],Y[1010], n, BE = 6, K,TT[2010], TP[1010];
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;
    srand(1897);
    scanf("%d",&K);
    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++){
        if(n >8){
        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);
        }
        }
        else{
        while(1){
            for(i=1;i<=2*n;i++){
                TP[i] = i;
                swap(TP[i],TP[rand()%i+1]);
            }
            for(i=1;i<=n;i++){
                TT[i]=X[i];
                TT[n+i]=Y[i];
            }
            TT[n+n+1]=TT[n+n+2]=0;
            int c1 = 0, c2 = 0;
            for(i=1;i<=n;i++){
                TT[TP[i]] += i;
                if(TP[i] <= n) TT[n+n+2] += i, c2++;
                else TT[n+n+1] += i, c1++;
            }
            for(i=n+1;i<=n+n;i++){
                TT[TP[i]] += n+1;
            }
            TT[n+n+2] += (n+1)* (n+1-c2);
            TT[n+n+1] += (n+1)* (n+1-c1);
            sort(TT+1,TT+n+n+3);
            for(i=1;i<=n+n+1;i++){
                if(TT[i]==TT[i+1])break;
            }
            if(i==n+n+2){
                break;
            }
        }
        for(i=1;i<=n;i++){
            if(TP[i] <= n){
                Ins(TP[i],n+1,i);
            }
            else{
                Ins(n+1,TP[i]-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
view save

correct output
QAQ
view save

user output
QAQ
view save

Test 2

Group: 1

Verdict: ACCEPTED

input
3
view save

correct output
QAQ
view save

user output
QAQ
view save

Test 3

Group: 1

Verdict: ACCEPTED

input
4
view save

correct output
3 4 3 4
3 1 1 2
4 4 3 2
2 2 1 1
view save

user output
1 1 2 2
1 2 3 3
1 2 3 4
4 3 4 4
view save

Test 4

Group: 1

Verdict: ACCEPTED

input
5
view save

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 
view save

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
view save

Test 5

Group: 1

Verdict: ACCEPTED

input
6
view save

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 
...
view save

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 
...
view save

Test 6

Group: 1

Verdict: ACCEPTED

input
7
view save

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 
...
view save

user output
6 1 1 1 1 1 5 
2 5 2 2 2 2 4 
3 3 4 3 3 3 3 
4 4 4 3 4 4 1 
5 5 5 5 2 5 7 
...
view save

Test 7

Group: 1

Verdict: ACCEPTED

input
8
view save

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 
...
view save

user output
6 1 1 1 1 1 5 6 
2 5 2 2 2 2 4 8 
3 3 4 3 3 3 3 2 
4 4 4 3 4 4 1 1 
5 5 5 5 2 5 7 8 
...
view save

Test 8

Group: 1

Verdict: ACCEPTED

input
9
view save

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 
...
view save

user output
6 1 1 1 1 1 5 6 9 
2 5 2 2 2 2 4 8 9 
3 3 4 3 3 3 3 2 8 
4 4 4 3 4 4 1 1 1 
5 5 5 5 2 5 7 8 4 
...
view save

Test 9

Group: 1

Verdict: ACCEPTED

input
10
view save

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 
...
view save

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 
...
view save

Test 10

Group: 2

Verdict: ACCEPTED

input
3
view save

correct output
QAQ
view save

user output
QAQ
view save

Test 11

Group: 2

Verdict: ACCEPTED

input
4
view save

correct output
3 4 3 4
3 1 1 2
4 4 3 2
2 2 1 1
view save

user output
1 1 2 2
1 2 3 3
1 2 3 4
4 3 4 4
view save

Test 12

Group: 2

Verdict: ACCEPTED

input
29
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
26 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
view save

Test 13

Group: 2

Verdict: ACCEPTED

input
48
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
46 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
view save

Test 14

Group: 2

Verdict: ACCEPTED

input
80
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
78 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
view save

Test 15

Group: 2

Verdict: ACCEPTED

input
97
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
94 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
view save

Test 16

Group: 3

Verdict: ACCEPTED

input
3
view save

correct output
QAQ
view save

user output
QAQ
view save

Test 17

Group: 3

Verdict: ACCEPTED

input
4
view save

correct output
3 4 3 4
3 1 1 2
4 4 3 2
2 2 1 1
view save

user output
1 1 2 2
1 2 3 3
1 2 3 4
4 3 4 4
view save

Test 18

Group: 3

Verdict: ACCEPTED

input
111
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
110 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

Test 19

Group: 3

Verdict: ACCEPTED

input
506
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
506 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

Test 20

Group: 3

Verdict: ACCEPTED

input
844
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
842 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

Test 21

Group: 3

Verdict: ACCEPTED

input
991
view save

correct output
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
990 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

Tasks

A Ice cream-B Mex value-C Tunnels-D Program-E Grid-F Witch game-G Family reunion-

Submissions (ainta1)

3:47:43 1003:39:56 653:26:41 653:18:19 03:16:12 03:15:33 03:14:32 0