結果
問題 | No.2667 Constrained Permutation |
ユーザー | chineristAC |
提出日時 | 2024-03-08 23:24:33 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,548 bytes |
コンパイル時間 | 746 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 255,380 KB |
最終ジャッジ日時 | 2024-03-08 23:25:08 |
合計ジャッジ時間 | 31,611 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
58,340 KB |
testcase_01 | AC | 46 ms
58,340 KB |
testcase_02 | AC | 58 ms
66,496 KB |
testcase_03 | AC | 64 ms
71,000 KB |
testcase_04 | AC | 100 ms
78,000 KB |
testcase_05 | AC | 55 ms
66,492 KB |
testcase_06 | AC | 94 ms
77,868 KB |
testcase_07 | AC | 55 ms
66,496 KB |
testcase_08 | AC | 101 ms
77,860 KB |
testcase_09 | AC | 104 ms
77,868 KB |
testcase_10 | AC | 62 ms
68,548 KB |
testcase_11 | AC | 91 ms
77,900 KB |
testcase_12 | AC | 573 ms
126,240 KB |
testcase_13 | AC | 97 ms
78,268 KB |
testcase_14 | AC | 1,666 ms
233,736 KB |
testcase_15 | AC | 969 ms
151,436 KB |
testcase_16 | AC | 691 ms
132,080 KB |
testcase_17 | AC | 271 ms
89,800 KB |
testcase_18 | AC | 1,710 ms
241,528 KB |
testcase_19 | AC | 1,591 ms
183,128 KB |
testcase_20 | AC | 1,703 ms
166,136 KB |
testcase_21 | AC | 1,237 ms
181,632 KB |
testcase_22 | AC | 1,219 ms
170,776 KB |
testcase_23 | AC | 1,271 ms
181,912 KB |
testcase_24 | AC | 718 ms
155,072 KB |
testcase_25 | AC | 1,341 ms
213,668 KB |
testcase_26 | AC | 1,688 ms
255,380 KB |
testcase_27 | AC | 1,695 ms
250,932 KB |
testcase_28 | WA | - |
testcase_29 | AC | 928 ms
200,316 KB |
testcase_30 | WA | - |
testcase_31 | AC | 627 ms
170,676 KB |
testcase_32 | WA | - |
testcase_33 | AC | 637 ms
97,472 KB |
testcase_34 | AC | 316 ms
87,872 KB |
testcase_35 | AC | 371 ms
89,920 KB |
testcase_36 | AC | 366 ms
88,952 KB |
testcase_37 | AC | 389 ms
90,984 KB |
testcase_38 | AC | 933 ms
133,036 KB |
testcase_39 | AC | 117 ms
78,484 KB |
testcase_40 | AC | 241 ms
86,296 KB |
testcase_41 | AC | 419 ms
97,660 KB |
testcase_42 | AC | 821 ms
135,200 KB |
testcase_43 | AC | 1,174 ms
140,428 KB |
testcase_44 | AC | 494 ms
106,740 KB |
testcase_45 | AC | 91 ms
78,104 KB |
ソースコード
import sys from itertools import permutations from heapq import heappop,heappush from collections import deque import random import bisect input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) class SegmentTree: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num self.size = n for i in range(n): self.tree[self.num + i] = init_val[i] for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): k += self.num self.tree[k] = x while k > 1: k >>= 1 self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1]) def query(self, l, r): if r==self.size: r = self.num res = self.ide_ele l += self.num r += self.num right = [] while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: right.append(self.tree[r-1]) l >>= 1 r >>= 1 for e in right[::-1]: res = self.segfunc(res,e) return res def checK_zero(N,_lr): lr = _lr[:] lr.sort(key=lambda x:x[0],reverse=True) nxt_num = 0 pq = [] while lr or pq: while lr and lr[-1][0] <= nxt_num: l,r = lr.pop() heappush(pq,r) #print(lr,pq,nxt_num) if pq: r = heappop(pq) if r < nxt_num: #print("ban!",pq,lr,nxt_num) return False nxt_num += 1 else: l,r = lr[-1] nxt_num = l return True def check_k(N,k,_lr): lr = [(l-k,r-k) for l,r in _lr] lr.sort(key=lambda x:x[0],reverse=True) pq = [] for i in range(1,N+1): while lr and lr[-1][0] <= i: heappush(pq,lr.pop()[1]) if not pq: return False r = heappop(pq) if r < i: return False return True def solve_brute(N,lr): res = [] R = max(r for l,r in lr) for k in range(-N,R+1): if check_k(N,k,lr): res.append(k) return res def solve(N,_lr): if not checK_zero(N,_lr): return 0 return [] lr = [(l,r+1) for l,r in _lr] """ 結婚定理で考える 区間の和集合が区間になるような組のみ考えればいい (区間の長さ)< (区間の数) である組があれば答えは0 = 相異なる整数を割り当てられるか? そうでないなら条件を満たすkの範囲は区間になっているので、端点を考えればいい """ val_set = set() for i,(l,r) in enumerate(lr): val_set.add(l) val_set.add(r) val_set = sorted(val_set) comp = {e:i for i,e in enumerate(val_set)} lr = [(comp[l],comp[r]) for l,r in lr] lr.sort(key=lambda x:x[0],reverse=True) n = len(comp) cnt = [0] * (n) for l,r in lr: cnt[l] += 1 cnt[r] -= 1 for i in range(1,n): cnt[i] += cnt[i-1] if 0 in cnt[:n-1]: return [] L,R = -10**9,10**9 for i,(l,r) in enumerate(lr): t = i + 1 ll = val_set[l] L = max(L,t-N+ll-1) lr.sort(key=lambda x:(x[1],x[0]),reverse=False) for i,(l,r) in enumerate(lr): t = i + 1 rr = val_set[r] - 1 R = min(R,rr-t) #print("LR",L,R) if L <= R: return R-L+1 return [k for k in range(L,R+1)] else: return 0 return [] def make_test(N): lr = [] for i in range(N): l = random.randint(1,2*N) r = random.randint(l,2*N) lr.append((l,r)) return lr while False: N = random.randint(1,10) lr = make_test(N) #N = 2 #lr = [(1,4),(4,4)] #N = 3 #lr = [(5,6),(6,6),(5,5)] #N = 4 #lr = [(1,5),(5,7),(3,7),(7,7)] #N = 4 #lr = [(2,7),(2,4),(4,6),(3,3)] res = solve(N,lr) exp = solve_brute(N,lr) if res != exp: print("WA") print(N) print(lr) print("res",res) print("exp",exp) break else: print("AC",N) N = int(input()) lr = [tuple(mi()) for i in range(N)] print(solve(N,lr))