Submission #28513

#	Time	Username	Problem	Language	Result	Execution time	Memory
28513		ㅁㄴㅇㄹ (#68)	Test Data Creation (FXCUP2_testdata)	C++14	0 / 1	0 ms	1852 KiB

testdata

#include <bits/stdc++.h>
#include <unistd.h>

#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define lld long long
#define Inf 1000000000
#define get gett

using namespace std;

int N,M;
int a[302][302],d[302][302][602];
pii patht[302][302];
int dt[302][302],pathtt[302][302],print[302][302];
bool check[302][302],tcheck[302][302];
priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> q;
pii get;
vector<pii> tmp;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
struct data{
    int x,y,z;
    data(){}
    data(int x,int y,int z):x(x),y(y),z(z){}
}path[302][302][602];

pii change(int i,int j){
	int tmp = (i-1)*M+j-1;
	return pii(tmp/N+1,tmp%N+1);
}
pii change2(int i,int j,int k){
	// j <= N
	if(j == N){
		if(k <= j) return pii(i,k);
		else return pii(i-(k-N),N);
	}else{
		if(k <= j) return pii(i,k);
		else if(k <= N) return pii(i-1,k);
		else return pii(i-(k-N)-1,N);
	}
}

void init(int i,int j){
	int x,y,range;

	tmp.clear();
	get = change(i,j);
	x = get.first; y = get.second;
	if(i == 1 && j <= N) range = j;
	else if(y == N) range = N+x-1;
	else range = N+x-2;
	for(int k=1; k<=range; k++){
		get = change2(x,y,k);
		q.push({d[i][j][k],{get.first,get.second}});
		tmp.pb(get);
		check[get.first][get.second] = true;
	}
}

int getvalue(int x,int y){
	int tmp = (x-1)*N+y-1;
	return a[tmp/M+1][tmp%M+1];
}

void calc(){
	for(auto &i : tmp){
		tcheck[i.first][i.second] = false;
		dt[i.first][i.second] = Inf;
	}
	while(!q.empty()){
		int value,x,y;
		value = q.top().first;
		x = q.top().second.first;
		y = q.top().second.second;
		q.pop();
		if(tcheck[x][y]) continue;
		tcheck[x][y] = true;
		dt[x][y] = value;
		for(int i=0; i<4; i++){
			if(!check[x+dx[i]][y+dy[i]]) continue;
			if(dt[x+dx[i]][y+dy[i]] > value+getvalue(x+dx[i],y+dy[i])){
				dt[x+dx[i]][y+dy[i]] = value+getvalue(x+dx[i],y+dy[i]);
				q.push({dt[x+dx[i]][y+dy[i]],{x+dx[i],y+dy[i]}});
				patht[x+dx[i]][y+dy[i]] = {x,y};
			}
		}
	}
	for(auto &i : tmp){
		check[i.first][i.second] = false;
        int x,y;
        vector<pii> memo;

        x = i.first; y = i.second;
        while(patht[x][y].first != 0){
            memo.pb({x,y});
            pii ttt = patht[x][y];
            x = ttt.first; y = ttt.second;
        }
        for(auto &i : memo){
            patht[i.first][i.second] = {x,y};
        }
	}
}

void calc2(int i,int j){
    int x,y;
    get = change(i,j);
    x = get.first; y = get.second;
    for(auto &i : tmp){
        int t,tx,ty;
        tx = patht[i.first][i.second].first;
        ty = patht[i.first][i.second].second;
        if(tx == x) t = ty;
        else if(y == N){
            t = N-tx+x;
        }else{
            if(tx== x-1) t = ty;
            else t = N-tx+x-1;
        }
        pathtt[i.first][i.second] = t;
    }
}

int lastd[302][302];
pii plpath[302][302];
void lastcalc(){
    lastd[1][1] = 0;
    for(int i=1; i<=M; i++){
        for(int j=1; j<=N; j++){
            if(i == 1 && j == 1) continue;
            lastd[i][j] = Inf;
            if(j > 1 && lastd[i][j] > lastd[i][j-1]){
                lastd[i][j] = lastd[i][j-1];
                plpath[i][j] = {i,j-1};
            }
            if(i > 1 && lastd[i][j] > lastd[i-1][j]){
                lastd[i][j] = lastd[i-1][j];
                plpath[i][j] = {i-1,j};
            }
            if(print[i][j] == 0) lastd[i][j] += getvalue(i,j);
        }
    }
    int x,y;
    x = M; y = N;
    while(x != 0){
        print[x][y] = true;
        pii ttt = plpath[x][y];
        x = ttt.first; y = ttt.second;
    }
}

int main(){
    //freopen("input.txt","r",stdin);
	scanf("%d %d",&N,&M);
	bool flag = false;
	if(N > M){
        swap(N,M);
        flag = true;
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			scanf("%d",&a[i][j]);
		}
	}
	d[1][1][1] = a[1][1];
	path[1][1][1] = data(0,0,0);
	for(int i=2; i<=N; i++){
		for(int j=1; j<=i; j++){
			d[1][i][j] = d[1][i-1][1]+a[1][i];
			path[1][i][j] = data(1,i-1,j);
		}
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			if(i == 1 && j <= N) continue;
			int x,y,bx,by,range;

			get = change(i,j);
			x = get.first; y = get.second;
            if(y == N) range = N+x-1;
            else range = N+x-2;
			for(int k=1; k<=range; k++) d[i][j][k] = Inf;

			if(j != 1){
				init(i,j-1);
				get = change(i,j-1);
				bx = get.first; by = get.second;
				while(!(bx == x && by == y)){
					if(!check[bx][by]){
						check[bx][by] = true;
						tmp.pb({bx,by});
					}
					by++;
					if(by == N+1){
						by = 1;
						bx++;
					}
				}
				for(int k=1; k<=range; k++){
					get = change2(x,y,k);
					if(!check[get.first][get.second]){
						check[get.first][get.second] = true;
						tmp.pb(get);
					}
				}
				calc();
				calc2(i,j-1);
				for(int k=1; k<=range; k++){
					get = change2(x,y,k);
					int ttt;
					if(k == y) ttt = 0;
					else ttt = a[i][j];
					if(d[i][j][k] > dt[get.first][get.second]+ttt){
						d[i][j][k] = dt[get.first][get.second]+ttt;
						path[i][j][k] = data(i,j-1,pathtt[get.first][get.second]);
					}
				}
			}
			if(i != 1){
				init(i-1,j);
				get = change(i-1,j);
				bx = get.first; by = get.second;
				while(!(bx == x && by == y)){
					if(!check[bx][by]){
						check[bx][by] = true;
						tmp.pb({bx,by});
					}
					by++;
					if(by == N+1){
						by = 1;
						bx++;
					}
				}
				for(int k=1; k<=range; k++){
					get = change2(x,y,k);
					if(!check[get.first][get.second]){
						check[get.first][get.second] = true;
						tmp.pb(get);
					}
				}
				calc();
				calc2(i-1,j);
				for(int k=1; k<=range; k++){
					get = change2(x,y,k);
					int ttt;
					if(k == y) ttt = 0;
					else ttt = a[i][j];
					if(d[i][j][k] > dt[get.first][get.second]+ttt){
						d[i][j][k] = dt[get.first][get.second]+ttt;
						path[i][j][k] = data(i-1,j,pathtt[get.first][get.second]);
					}
				}
			}
		}
	}
    printf("%d\n",d[N][M][M]);
    int x,y,z;
    x = N; y = M; z = M;
    while(x != 0){
        data dtmp = path[x][y][z];
        print[x][y] = 1;
        x = dtmp.x; y = dtmp.y; z = dtmp.z;
    }
    vector<int> vprint;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) vprint.pb(print[i][j]);
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) print[i][j] = 0;
    for(int i=1; i<=M; i++){
        for(int j=1; j<=N; j++) print[i][j] = vprint[(i-1)*N+j-1];
    }
    vprint.clear();
    lastcalc();
    for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) vprint.pb(print[i][j]);
    if(!flag) swap(N,M);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) printf("%d ",vprint[(i-1)*M+j-1]);
        puts("");
    }

	return 0;
}

Compilation message (stderr)

testdata.cpp: In function 'int main()':
testdata.cpp:156:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
testdata.cpp:164:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][j]);
                        ^

• Subtask 1: 0 / 1