제출 #101044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101044		autumn_eel	Amusement Park (JOI17_amusement_park)	C++14	68 / 100	71 ms	6456 KiB

Joi

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
 
#include "Joi.h"
 
vector<int>E[20000];
vector<int>vs;
bool used[20000];
 
void dfs(int v,int p){
	used[v]=true;
	vs.push_back(v);
	for(int u:E[v]){
		if(used[u])continue;
		dfs(u,v);
		vs.push_back(v);
	}
}
 
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	rep(i,M){
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	dfs(0,-1);
	set<int>se1,se2;
	mt19937 mt(123456789);
	vector<int>V;
	rep(i,60)V.push_back(i);
	int MP[60]{};
	for(int v:vs){
		if(!se1.count(v)){
			se2.insert(v);
		}
		if(se2.size()==60){
			int cnt=0;
			shuffle(V.begin(),V.end(),mt);
			for(int i:se2){
				MP[V[cnt]]++;
				MessageBoard(i,X>>V[cnt]&1);
				cnt++;
			}
			for(int i:se2){
				se1.insert(i);
			}
			se2.clear();
		}
	}
	shuffle(V.begin(),V.end(),mt);
	int cnt=0;
	for(int i:se2){
		MP[V[cnt]]++;
		MessageBoard(i,X>>V[cnt]&1);
		cnt++;
	}
}

Ioi

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
 
#include "Ioi.h"
 
static vector<int>E[20000];
static vector<int>vs;
static int vid[20000];
static bool used[20000];
 
static void dfs(int v,int p){
	used[v]=true;
	vid[v]=vs.size();
	vs.push_back(v);
	for(int u:E[v]){
		if(used[u])continue;
		dfs(u,v);
		vs.push_back(v);
	}
}
 
long long Ioi(int N, int M, int A[], int B[], int Pos, int V, int T) {
	rep(i,M){
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	dfs(0,-1);
	set<int>se1,se2;
	map<int,int>id;
	mt19937 mt(123456789);
	vector<int>R;
	rep(i,60)R.push_back(i);
	for(int v:vs){
		if(!se1.count(v)){
			se2.insert(v);
		}
		if(se2.size()==60){
			shuffle(R.begin(),R.end(),mt);
			int cnt=0;
			for(int i:se2){
				id[i]=R[cnt];
				cnt++;
			}
			for(int i:se2){
				se1.insert(i);
			}
			se2.clear();
		}
	}
	int cnt=0;
	shuffle(R.begin(),R.end(),mt);
	for(int i:se2){
		id[i]=R[cnt];
		cnt++;
	}
	int x=vid[Pos];
	
	set<int>se;
	int r;
	for(r=x;r<vs.size();r++){
		se.insert(id[vs[r]]);
		if(se.size()==60)break;
	}
	if(r==vs.size())r=vs.size()-1;
	int l;
	for(l=x;l>=0;l--){
		se.insert(id[vs[l]]);
		if(se.size()==60)break;
	}
	if(l==-1)l=0;
	
	set<int>Se;
	int l2;
	for(l2=x;l2>=0;l2--){
		Se.insert(id[vs[l2]]);
		if(Se.size()==60)break;
	}
	if(l2==-1)l2=0;
	int r2;
	for(r2=x;r2<vs.size();r2++){
		Se.insert(id[vs[r2]]);
		if(Se.size()==60)break;
	}
	if(r2==vs.size())r2=vs.size()-1;
	if(r2-l2+min(r2-x,x-l2)<r-l+min(r-x,x-l)){
		swap(l,l2);
		swap(r,r2);
	}
	
	set<int>SE;
	int l3=x,r3=x;
	while(1){
		if(l3>0){
			SE.insert(id[vs[--l3]]);
		}
		if(r3<vs.size()-1){
			SE.insert(id[vs[++r3]]);
		}
		if(SE.size()==60)break;
	}
	
	if(r3-l3+min(r3-x,x-l3)<r-l+min(r-x,x-l)){
		swap(l,l3);
		swap(r,r3);
	}
	
	map<int,vector<int>>MP;
	rep(i,vs.size()){
		MP[id[vs[i]]].push_back(i);
	}
	int l4=x,r4=x;
	rep(i,60){
		int Min=INT_MAX;
		int t=-1;
		auto it=lower_bound(MP[i].begin(),MP[i].end(),x);
		if(it!=MP[i].end()){
			Min=*it-x;
			t=*it;
		}
		if(it!=MP[i].begin()){
			it--;
			if(Min>x-*it){
				Min=x-*it;
				t=*it;
			}
		}
		if(Min>900){
			abort();
		}
		l4=min(l4,*it);
		r4=max(r4,*it);
	}
	if(r4-l4+min(r4-x,x-l4)<r-l+min(r-x,x-l)){
		swap(l,l4);
		swap(r,r4);
	}
	
	ll ans=0;
	ans|=ll(V)<<id[Pos];
	if(abs(x-l)<abs(x-r)){
		//left
		for(int i=x-1;i>=l;i--){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
		for(int i=l+1;i<=r;i++){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
	}
	else{
		//right
		for(int i=x+1;i<=r;i++){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
		for(int i=r-1;i>=l;i--){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
	}
	return ans;
	
}

컴파일 시 표준 에러 (stderr) 메시지

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:63:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(r=x;r<vs.size();r++){
          ~^~~~~~~~~~
Ioi.cpp:67:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r==vs.size())r=vs.size()-1;
     ~^~~~~~~~~~~
Ioi.cpp:83:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(r2=x;r2<vs.size();r2++){
           ~~^~~~~~~~~~
Ioi.cpp:87:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r2==vs.size())r2=vs.size()-1;
     ~~^~~~~~~~~~~
Ioi.cpp:99:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r3<vs.size()-1){
      ~~^~~~~~~~~~~~
Ioi.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
Ioi.cpp:111:2: note: in expansion of macro 'rep'
  rep(i,vs.size()){
  ^~~
Ioi.cpp:117:7: warning: variable 't' set but not used [-Wunused-but-set-variable]
   int t=-1;
       ^

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 40 / 55
• Subtask 5: 0 / 17