#pragma region GNUC //https://yukicoder.me/wiki/auto_vectorization #ifdef __GNUC__ #pragma GCC optimize ("O3") #pragma GCC target ("avx") #endif #pragma endregion #define _USE_MATH_DEFINES #pragma region #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma endregion //#include ///////// #define REP(i, x, n) for(int i = x; i < n; ++i) #define rep(i,n) REP(i,0,n) ///////// #pragma region typedef long long LL; typedef long double LD; typedef unsigned long long ULL; #pragma endregion //typedef ////定数 const int INF = (int)1e9; const int MOD = (int)1e9+7; const LL LINF = (LL)1e18; ///////// using namespace::std; ///////// #pragma region Math // 最大公約数 template inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;} //inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);} // 最小公倍数 template inline T lcm(T a, T b){return a / gcd(a, b) * b;} //inline T lcm(T a, T b){return a * b / gcd(a, b);} template T powMod(T num,int n,T mod=MOD){ if( n == 0 ){ return (T)1; } T mul = num; T ans = (T)1; while(n){ if( n&1){ ans = (ans*mul)%mod; } mul = (mul*mul)%mod; n >>= 1; } return ans; } #pragma endregion //math #pragma region template void UNIQUE(vector& vec){ sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end() ); } #pragma endregion // sort erase unique //////////////////////////////// #pragma region long long bitcount64(long long bits) { bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555); bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333); bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f); bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff); bits = (bits & 0x0000ffff0000ffff) + (bits >>16 & 0x0000ffff0000ffff); return (bits & 0x00000000ffffffff) + (bits >>32 & 0x00000000ffffffff); } #pragma endregion //その他 //////////////////////////////// struct edge{int to;LL cost;}; edge make_edge(int to,LL cost){ edge ret = {to,cost}; return ret; } #pragma region //グラフ void dijkstra(int root,int V,vector& dist, vector< vector > G ){ priority_queue,vector >,greater > > que; dist.assign(V,LINF); dist[root] = 0; que.push(pair(0,root));//距離、頂点番号 while( !que.empty() ){ pair p = que.top();que.pop(); int v = p.second; if( dist[v] < p.first ) continue; for(int i=0;i < (int)G[v].size();++i){ edge e = G[v][i]; if( dist[e.to] > dist[v] + e.cost ){ dist[e.to] = dist[v] + e.cost; que.push(pair(dist[e.to],e.to)); } } } } #pragma endregion //ダイクストラ法:O(|E|log|V|) #pragma region //グラフ void warshall_floyd(vector >& dist,int V,const LL INF=LINF){ for(int k=0;k= INF ) continue; for(int j=0;j= INF )continue; dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]); } } } } #pragma endregion //ワーシャルフロイド:O(|V|**3) #pragma region //http://sugarknri.hatenablog.com/entry/2016/07/16/165715 //LL inv[1000010]; void makeinv(vector& inv,const LL P){ int i; inv = vector(1000010,0); inv[1]=1; for(i=2;i<=1000000;i++){ inv[i] = inv[P%i] * (P-P/i)%P;//OVF } } ULL nCk(ULL N,ULL k){ static vector inv; if( inv.size() == 0 ){ makeinv(inv,MOD); } k = min(k,N-k); if( k == 0 ){return 1;} if( k == 1 ){return N%MOD;} ULL ret = 1; for(int i=1;i<=k;++i){ ret *= ((N+1-i)*inv[i])%MOD;//OVF ret %= MOD; } return ret; } #pragma endregion //組み合わせnCk(,10^5) #pragma region CGL class Point{ public: double x,y; Point(double x=0,double y=0):x(x),y(y){} Point operator + (Point p){return Point(add(x,p.x),add(y,p.y));} void operator += (Point p){x=add(x,p.x);y=add(y,p.y);} Point operator - (Point p){return Point(add(x,-p.x),add(y,-p.y));} void operator -= (Point p){x=add(x,-p.x);y=add(y,-p.y);} Point operator * (double a){return Point(x*a,y*a);} double operator * (Point p){return dot(p);} Point operator / (double a){return Point(x/a,y/a);} double norm(){return sqrt(x*x+y*y);} double dot(Point p){return add(x*p.x,y*p.y);} double rot(Point p){return add(x*p.y,-y*p.x);} double add(double a,double b){ double EPS = 1e-10; if( abs(a+b) < EPS*(abs(a)+abs(b)) ){ return 0; } return a+b; } }; istream& operator>>(istream& in,Point& P){ in >> P.x >> P.y; return in; } //線分p1-p2上に点qがあるか判定 bool on_seg(Point p1,Point p2,Point q){ return (p1-q).rot(p2-q) == 0 && (p1-q).dot(p2-q) <= 0; } Point intersection(Point p1,Point p2,Point q1,Point q2){ return p1+(p2-p1)*((q2-q1).rot(q1-p1)/(q2-q1).rot(p2-p1)); } enum PointPotion{ON_SEGMENT,COUNTER_CLOCKWISE,ONLINE_BACK,CLOCKWISE,ONLINE_FRONT}; PointPotion ccw(Point A,Point B,Point C){ B -= A;C -=A; if( B.rot(C) > 0 ) return COUNTER_CLOCKWISE; if( B.rot(C) < 0 ) return CLOCKWISE; if( B.dot(C) < 0 ) return ONLINE_BACK; if( B.norm() < C.norm() ) return ONLINE_FRONT; return ON_SEGMENT; } #pragma endregion //class Point #pragma region //辞書順で比較 bool cmp_x(const Point& p,const Point& q){ if( p.x != q.x ) return p.x < q.x; return p.y < q.y; } //凸包を求める vector convex_hull(vector ps,int n){ sort(ps.begin(),ps.end(), cmp_x); int k = 0;//凸包の頂点数 vector qs(n*2);//構築中の凸包 //下側の凸包の作成 for(int i=0;i1 && (qs[k-1]-qs[k-2]).rot(ps[i]-qs[k-1]) <=0){ k--; } qs[k++] = ps[i]; } //上側凸包の作成 for(int i=n-2,t=k;i>=0;i--){ while(k>t && (qs[k-1]-qs[k-2]).rot(ps[i]-qs[k-1]) <=0){ k--; } qs[k++] = ps[i]; } qs.resize(k-1); return qs; } #pragma endregion //凸包 #pragma region template istream& operator>>(istream& in,pair P){ in >> P.first >> P.second; return in; } #pragma endregion //cin pair /* #pragma region //行列の積 vector< vector > operator*( vector >& A,vector< vector >& B){ LL mod = MOD; int R = A.size(); int cen = A[0].size(); int C = B[0].size(); vector< vector > ans(R,vector(C,0) ); for(int row=0;row > powMod(vector< vector > mat,LL N){ int R = mat.size(); int C = mat[0].size(); //R==C vector< vector > I(R,vector(C,0));//単位元 for(int i=0;i > mul(R,vector(C)),ans(R,vector(C)); ans = I; mul = mat; while(N){ if( N & 1 ){ ans = ans*mul; } N >>= 1; mul = mul*mul; } return ans; } #pragma endregion //行列 */ #pragma endregion // const double PI = acos(-1.0); const double EPS = 1e-9; ///////////////////// vector uni; bool cmp2(const vector& A,const vector& B){ LL Anum = ((LL)uni[A[2]]<<20)+A[1]; LL Bnum = ((LL)uni[B[2]]<<20)+B[1]; return Anum < Bnum; } void solve(){ int N,K; scanf("%d%d",&N,&K); uni = vector (N,0); vector ans(N); vector sco(11,0); vector< vector > data(N,vector(4)); for(int i=0;i >::iterator itr,begin,end,L,R; begin = data.begin(); end = data.end(); int T = 0; while(T temp(4,-1); temp[0] = data[T][0]+1; L = begin+T; R = L + sco[(*L)[0]*(-1)]; while(L