Codeforces Round #268 DIV1 B問題 (1000pt)
Codeforces Round #268 DIV2 D問題 (2000pt)
Problem description
$N$ 個の相異なる整数 $\{P_k\}_{k=1}^N$ が与えられる．
それぞれの整数について，集合 $X$ または集合 $Y$ のどちらか一方に含まれるように，振り分けたい．
この際，集合 $X$ に整数 $k$ が含まれる場合は，集合 $X$ に整数 $A-k$ が含まれてなければいけない，
および，集合 $Y$ に整数 $k$ が含まれる場合は，集合 $Y$ に整数 $B-k$ が含まれてなければいけない，
という $2$ つの条件を満たさなければいけない．
このような条件を満たす振りわけ方を $1$ つ求める問題．
存在しないならそれを指摘する．
各整数 $P_k$ について，どう頑張っても片方の集合にしか属することができない整数を見つけてきて，それから確定させていく．
確定させることにより，片方の集合にしか属すことができない要素がどんどん出てくるので，それらを順番に処理していく．
実際には，全ての整数を処理する候補を保存する配列に放り込んでおいて，処理していく．
両方の集合に属すことができるなら，とりあえず保留して処理する配列から放り出しておく．
片方の集合にしか属すことができない要素を見つけて，それを決めつけた時，もしかしたら片方の集合にしか属すことができなくなるかもしれない要素を改めて，処理する候補の配列に突っ込んで，処理する．
最終的に，両方の集合に属することができる要素のみになれば，それらをまとめて同じ集合（例えば $X$）に入れれば条件を満たすので，まとめて片方の集合に割り振る．
（実際にはこのようなことになるのは $A=B$ の場合のみであるはず）
途中で，頑張ってもどちらの集合にも属すことができない要素が出てきたら不可能．
以下のコードでは，整数 $P_k$ が互いに異なるという条件を読み落としたため，異ならない場合も考慮してしまった複雑なコードです．
時間計算量 $O(N)$．
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
template<class T>
struct ullHash{
ull *key; T *val; unsigned memory, size, mask;
void clear(){memset(val,0,size*sizeof(T));}
void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
int function(ull a){return (a*97531)&mask;}
T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};
#define INF 2000000000LL
int N, A, B;
int P[200000];
int res[200000];
int inv[200000];
ullHash<int> inA, inB, place, cnt;
int dame;
int docheck[1000000], dosz;
int isCan(int ind, int st){
int tar, all, used;
if(st==0){
tar = A - P[ind];
} else {
tar = B - P[ind];
}
if(tar <= 0) return 0;
if(tar == P[ind]) return 1;
if(st==0 && inA.get(tar)) return 1;
if(st==1 && inB.get(tar)) return 1;
all = cnt.get(tar);
used = inA.get(tar) + inB.get(tar);
if(all > used) return 1;
return 0;
}
int next_ind(int v){
int used = inA.get(v) + inB.get(v);
return place.get(INF*(used+1)+v) - 1;
}
int main(){
int i, j, k;
int fgA, fgB;
int used, cur, tar, tt, ccc;
reader(&N,&A,&B);
rep(i,N) reader(P+i);
rep(i,N) res[i] = -1;
inA.init(200000, 200000);
inB.init(200000, 200000);
place.init(200000, 200000);
cnt.init(200000, 200000);
rep(i,N){
k = cnt.increase(P[i]);
inv[i] = k;
place.set(INF*k+P[i], i+1);
}
dosz = 0;
rep(i,N) docheck[dosz++] = i;
while(dosz){
i = docheck[--dosz];
if(res[i] >= 0) continue;
used = inA.get(P[i]) + inB.get(P[i]);
ccc = inv[i];
if(used + 1 != ccc) continue;
fgA = isCan(i, 0);
fgB = isCan(i, 1);
if(fgA && fgB) continue;
if(!fgA && !fgB){ dame=1; break; }
if(fgA){
res[i] = 0; used++;
inA.increase(P[i]);
tar = A - P[i];
if(inA.get(tar)==0){
j = next_ind(tar);
inA.increase(P[j]);
res[j] = 0;
tt = B - tar;
k = next_ind(tt);
if(tt >= 0) docheck[dosz++] = k;
}
j = next_ind(P[i]);
if(j >= 0) docheck[dosz++] = j;
} else {
res[i] = 1; used++;
inB.increase(P[i]);
tar = B - P[i];
if(inB.get(tar)==0){
j = next_ind(tar);
inB.increase(P[j]);
res[j] = 1;
tt = A - tar;
k = next_ind(tt);
if(tt >= 0) docheck[dosz++] = k;
}
j = next_ind(P[i]);
if(j >= 0) docheck[dosz++] = j;
}
}
rep(i,N) if(res[i]==-1) res[i] = 0;
if(dame){
puts("NO");
} else {
puts("YES");
rep(i,N) printf("%d%c",res[i],i==N-1?'\n':' ');
}
myed;
return 0;
}
Current time: 2024年04月20日19時34分05秒
Last modified: 2014年09月24日06時17分35秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF268 CF_Div1_B CF_Div2_D
トップページに戻る
Logged in as: unknown user (not login)