QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742465#7949. K-Lotteryyuto1115#TL 0ms3836kbC++204.1kb2024-11-13 16:39:422024-11-13 16:39:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 16:39:43]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3836kb
  • [2024-11-13 16:39:42]
  • 提交

answer

#include<bits/stdc++.h>
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define eb emplace_back
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto b) {return a>b ? a=b, 1 : 0;}
bool chmax(auto& a, auto b) {return a<b ? a=b, 1 : 0;}

const int mod = 1000000007;

struct mint {
	ll x;
	mint(ll x=0) : x((x%mod+mod)%mod) {}

	mint &operator+=(mint a) { if((x += a.x) >= mod) x -= mod; return *this; }
	mint &operator-=(mint a) { if((x += mod-a.x) >= mod) x -= mod; return *this; }
	mint &operator*=(mint a) { (x *= a.x) %= mod; return *this; }

	mint operator+(mint a) { return mint(*this) += a; }
	mint operator-(mint a) { return mint(*this) -= a; }
	mint operator*(mint a) { return mint(*this) *= a; }

	mint pow(ll t) {
		mint res(1), a(*this);
		while(t) {
			if(t&1) res *= a;
			a *= a;
			t >>= 1;
		}
		return res;
	}

	mint inv() { return pow(mod-2); }
};

using vm = vector<mint>;

using T = pair<mint, int>;
using S = mint;

struct lazy_segment_tree {
	ll n;
	ll LOG;
	vector<T> node;
	vector<S> lazy;
	T vINF;
	S lINF;
	lazy_segment_tree(const vector<T> &x, T vINF_, S lINF_){
		vINF = vINF_;
		lINF = lINF_;
		n = 1;
		LOG = 1;
		while(n <= x.size()) n *= 2, LOG++;
		node.resize(2*n, vINF);
		lazy.resize(2*n, lINF);
		rep(i,SZ(x)) node[i+n] = x[i];
		rrep(i,n) node[i] = compare(node[i*2], node[i*2+1]);
	}
	T compare(T l, T r){
		return {l.first + r.first, l.second + r.second};
	}
	T add1(T l, S r){
		return {l.first * r, l.second};
	}
	S add2(S l, S r){
		return l * r;
	}

	void eval(ll idx){
		node[idx] = add1(node[idx], lazy[idx]);
		if(idx < n){
			lazy[idx*2] = add2(lazy[idx*2], lazy[idx]);
			lazy[idx*2+1] = add2(lazy[idx*2+1], lazy[idx]);
		}
		lazy[idx] = lINF;
	}

	void update(ll idx, T val){
		ll now = idx + n;
		node[now] = val;
		while(now > 0){
			now >>= 1;
			eval(now), eval(now*2), eval(now*2+1);
			node[now] = compare(node[now*2], node[now*2+1]);
		}
	}

	void add(ll l, ll r, S val, ll now = 1, ll left = 0, ll right = -1){
		if(right == -1) right = n;
		eval(now);
		if(l <= left && right <= r){
			lazy[now] = add2(lazy[now], val);
			eval(now);
			return;
		}
		if(r <= left || right <= l) return;
		ll mid = (left+right)/2;
		add(l, r, val, now*2, left, mid);
		add(l, r, val, now*2+1, mid, right);
		node[now] = compare(node[now*2], node[now*2+1]);

	}

	T calc(ll l, ll r, ll now = 1, ll left = 0, ll right = -1){
		if(right == -1) right = n;
		eval(now);
		if(l <= left && right <= r) return node[now];
		if(r <= left || right <= l) return vINF;
		ll mid = (left+right)/2;
		return compare(calc(l,r,now*2,left,mid), calc(l,r,now*2+1,mid,right));
	}
};

mt19937_64 engine(2111);
uniform_int_distribution<int> dist(0, mod-1);
const mint r = mint(dist(engine));

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int k,m,n;
	cin >> k >> m >> n;
	vvl tc(m, vl(k));
	rep(i,m) rep(j,k) cin >> tc[i][j];
	vl v(n);
	rep(i, n) cin >> v[i];
	vl cp = v;
	sort(all(cp));
	for(ll &i : v) i = lower_bound(all(cp), i) - cp.begin();
	lazy_segment_tree st(vector<T>(n, make_pair(0,0)), {0,0}, 1);
	vm pw(n+1);
	pw[0] = 1;
	rep(i, n) pw[i+1] = pw[i] * r;
	auto add = [&](int i, ll x) {
		st.add(i+1, n, r);
		int cnt = st.calc(0,i).second;
		st.update(i, {pw[cnt] * x, 1});
	};
	mint r_iv = mint(r).inv();
	auto del = [&](int i) {
		st.add(i+1, n, r_iv);
		st.update(i, {0,0});
	};
	map<ll, int> mp;
	rep(i, m) {
		vl pos(k);
		iota(all(pos), 0);
		sort(all(pos), [&](int a, int b) { return tc[i][a] < tc[i][b]; });
		mint val = 0;
		rep(j, k) val += pw[j] * pos[j];
	        mp[val.x] = i;	
	}
	mint sum = 0;
	rep(i, k) sum += pw[i];
	rep(i, n) {
		if(i >= k) del(v[i-k]);
		add(v[i], i);
		if(i >= k-1) {
			mint val = st.calc(0, n).first;
			val -= sum * (i-k+1);
			if(mp.count(val.x)) {
				int idx = mp[val.x];
				rep(j, k) cout << tc[idx][j] << " \n"[j==k-1];
				return 0;
			}
		}
	}
	cout << 0 << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

3 2 10
1 2 3
1 3 2
20 35 10 7 99 53 72 33 88 16

output:

1 3 2

result:

ok single line: '1 3 2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4 5 10
1 2 3 4
1 2 4 3
3 4 1 2
4 1 2 3
4 2 3 1
19 31 9 1 89 48 63 30 78 12

output:

4 2 3 1

result:

ok single line: '4 2 3 1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3 3 7
1 3 2
2 3 1
2 1 3
11 22 33 44 55 66 77

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Time Limit Exceeded

input:

10000 10 1000000
1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5...

output:


result: