提出 #2179162

---

ソースコード 拡げる

// zigzag 8
//#pragma GCC optimize ("O3")
//#pragma GCC target ("tune=native")
//#pragma GCC target ("avx")
#include <random>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PPI;
typedef pair<ll,P> PIP;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define PQ2(T) priority_queue<T>
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define REP(i,a,b) for(ll (i)=a;(i)<(ll)(b);++(i))
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) ((x)=min((x),(y)))
#define chmax(x,y) ((x)=max((x),(y)))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
#define DEBUG(x) cerr<<"line ("<<__LINE__<<")  "<<#x<<": "<<x<<endl;
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
mt19937_64 rng;
random_device seed_gen;

#define N 40
#define M 1000
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int n, m;
int a[M], b[M], c[M], d[M];
int g[N][N];
vector<int> res(M, -1);
int sc = 0;

ll sqr(ll x){ return x*x; }
void init();
void input();
void solve();
void output();
vector<int> calc(vector<int> &r);
int score(vector<int> &r);
int mk_dist(int gg[N][N], int gg2[N][N], int s, int t);

int main(){
	init();
	input();
	solve();
	output();
	return 0;
}

void init(){
	rng = mt19937_64(123457);
}
void input(){
	scanf("%d%d",&n,&m);
	rep(i, m) scanf("%d%d%d%d",a+i,b+i,c+i,d+i);
	rep(i, m){
		g[a[i]][b[i]] = i+1;
		g[c[i]][d[i]] = -(i+1);
	}
}
#define C 8
void solve(){
	vector<int> x;
	rep(i, n) rep(j, n) if(g[i][j]==0) x.pb(i*n+j);
	shuffle(all(x), rng);
	rep(_, 1){
	vector<int> r[C];
	rep(k, C) r[k] = vector<int>(m, -1);
	rep(k, C){
		r[k] = vector<int>(m+1, -1);
		int w[N][N] = {};
		vector<int> ii(19);
		rep(i, 19) ii[i] = i;
		ii[0] = 9;
		rep(i, 9){
			ii[i*2+1] = 9+i+1;
			ii[i*2+2] = 9-i-1;
		}
		//rotate(ii.begin(), ii.begin()+9, ii.end());
		//shuffle(all(ii), rng);
		rep(i2, 19){
			int i = ii[i2];
			rep(j, 39){
				int x = (k/2%2?(i*2+1):n-(i*2+1)-1);
				int y = (i%2==k%2?j:n-j-1);
				if(k/4%2) swap(x, y);
				r[k][i2*39+j] = x*n+y;
				w[x][y] ^= 1;
				if(i2==18&&j==38){
					if(x==2) x--;
					if(x==n-3) x++;
					if(y==2) y--;
					if(y==n-3) y++;
					r[k][i2*39+j+1] = x*n+y;
				}
			}
		}
		
		for(int i = 19*39+1; i < m; i++){
			int cnt = w[a[i]][b[i]]+w[c[i]][d[i]];
			if(cnt!=1) continue;
			if(w[a[i]][b[i]]){
				r[k][i+1] = r[k][i] = a[i]*n+b[i];
			} else {
				r[k][i+1] = r[k][i] = c[i]*n+d[i];
			}
			i++;
		}
		int tmp = score(r[k]);
		//cerr<<k<<": "<<tmp<<endl;
		if(tmp>sc){
			sc = tmp;
			res = r[k];
		}
	}
	}
}
void output(){
	rep(i, m){
		if(res[i]==-1) printf("-1 -1\n");
		else printf("%d %d\n", res[i]/n, res[i]%n);
	}
}
vector<int> calc(vector<int> &r){
	vector<int> x(m, 0);
	int gg[N][N] = {}, gg2[N][N] = {};
	rep(i, m){
		if(r[i]>=0){
			//cerr<<i<<" "<<r[i]<<endl;
			gg[r[i]/n][r[i]%n] ^= 1;
		}
		//cerr<<i<<endl;
		int len = mk_dist(gg, gg2, a[i]*n+b[i], c[i]*n+d[i]);
		//cerr<<i<<"x"<<endl;
		if(len<0) x[i] = 0;
		else x[i] = sqr(len);
	}
	return x;
}
int score(vector<int> &r){
	vector<int> x = calc(r);
	int sum = 0;
	//cerr<<"xsize "<<x.size()<<" "<<m<<endl;
	rep(i, m) sum += x[i];
	return sum;
}
int mk_dist(int gg[N][N], int gg2[N][N], int s, int t){
	//cerr<<"mk_dist"<<s<<" "<<t<<endl;
	memset(gg2, -1, sizeof(int)*N*N);
	//rep(i, n) rep(j, n) if(gg[i][j]) gg2[i][j] = INF;
	int sx = s/n, sy = s%n, tx = t/n, ty = t%n;
	if(gg[sx][sy]) return 0;
	gg2[sx][sy] = 0;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int xy = q.front(); q.pop();
		int x = xy/n, y = xy%n;
		rep(i, 4){
			int x2 = x+dx[i], y2 = y+dy[i];
			if(x2<0||x2>=n||y2<0||y2>=n||gg[x2][y2]||gg2[x2][y2]>=0) continue;
			gg2[x2][y2] = gg2[x][y]+1;
			q.push(x2*n+y2);
		}
	}
	//cerr<<"mk_dist done"<<endl;
	return gg2[tx][ty];
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘void input()’:
./Main.cpp:94:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
./Main.cpp:95:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i, m) scanf("%d%d%d%d",a+i,b+i,c+i,d+i);
                                             ^

ジャッジ結果