Unfortunately we were unable to fully decode your file, as it is not encoded in UTF-8.
You can try to decode it yourself by downloading it here.
//test sprawdzaj�cy szybko�� find-union z biblioteczki earla //Krzysztof Kleiner #include<cstdio> #include<algorithm> #define FOR(i, b, n) for ( int (i) = b; (i) < (n); (i)++) #define FORR(i, b, n) for ( (i) = b; (i) < (n); (i)++) #define REP(i, n) for ( int (i) = 0; (i) < (n); (i)++) #define SC(n) scanf("%d", &(n)) #define SC2(n, m) scanf("%d%d", &(n), &(m)) #define SCLL(n) scanf("%lld", &(n)) #define PRT(n) printf("%d ", (n)) #define PRTLL(n) printf("%lld ", (n)) #define NXL printf("\n") typedef long long LL; typedef unsigned long long ULL; using namespace std; const int MAXN=50020; int w; struct car { int w, xstart, xstop, ind; }; car a[MAXN], temp[MAXN]; int suf[MAXN], sufind[MAXN]; bool mergesort (int p, int q) { if(p==q) return 1; int s = (p+q)/2; if(! mergesort(p, s) ) return 0; if(! mergesort(s+1, q) ) return 0;; suf[s] = a[s].w; sufind[s] = a[s].ind; for (int i = s-1; i>=p; i--) { if(suf[i+1] > a[i].w) sufind[i] = sufind[i+1]; else sufind[i] = a[i].ind; suf[i] = max(suf[i+1], a[i].w); } for (int i=p, j=s+1, b = p; i<=s || j<=q; ) { if(j>q || (i<=s && a[i].xstop <= a[j].xstop)) temp[b++] = a[i++]; else if(i > s) { temp[b++] = a[j++]; } else { if(a[j].w + suf[i] > w) { // printf("%d: %d %d %d %d %d bo %d\n", a[j].ind, a[j].w, a[j].xstart, a[j].xstop, suf[i], w, sufind[i]); return 0; } temp[b++] = a[j++]; } } for (int i=p; i<=q; i++) a[i] = temp[i]; return 1; } int main() { int z; SC(z); while(z--) { int n; SC2(n, w); REP(i, n) { int x1, y1, x2, y2; SC2(x1, y1); SC2(x2, y2); a[i].w = abs(y1 - y2); a[i].xstart = min(x1, x2); a[i].ind = i; } REP(i, n) { int x1, y1, x2, y2; SC2(x1, y1); SC2(x2, y2); a[i].xstop = min(x1, x2); } sort(a, a+n, [](car c, car d) { return c.xstart < d.xstart; }); if(mergesort(0, n-1)) printf("TAK\n"); else printf("NIE\n"); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | //test sprawdzaj�cy szybko�� find-union z biblioteczki earla //Krzysztof Kleiner #include<cstdio> #include<algorithm> #define FOR(i, b, n) for ( int (i) = b; (i) < (n); (i)++) #define FORR(i, b, n) for ( (i) = b; (i) < (n); (i)++) #define REP(i, n) for ( int (i) = 0; (i) < (n); (i)++) #define SC(n) scanf("%d", &(n)) #define SC2(n, m) scanf("%d%d", &(n), &(m)) #define SCLL(n) scanf("%lld", &(n)) #define PRT(n) printf("%d ", (n)) #define PRTLL(n) printf("%lld ", (n)) #define NXL printf("\n") typedef long long LL; typedef unsigned long long ULL; using namespace std; const int MAXN=50020; int w; struct car { int w, xstart, xstop, ind; }; car a[MAXN], temp[MAXN]; int suf[MAXN], sufind[MAXN]; bool mergesort (int p, int q) { if(p==q) return 1; int s = (p+q)/2; if(! mergesort(p, s) ) return 0; if(! mergesort(s+1, q) ) return 0;; suf[s] = a[s].w; sufind[s] = a[s].ind; for (int i = s-1; i>=p; i--) { if(suf[i+1] > a[i].w) sufind[i] = sufind[i+1]; else sufind[i] = a[i].ind; suf[i] = max(suf[i+1], a[i].w); } for (int i=p, j=s+1, b = p; i<=s || j<=q; ) { if(j>q || (i<=s && a[i].xstop <= a[j].xstop)) temp[b++] = a[i++]; else if(i > s) { temp[b++] = a[j++]; } else { if(a[j].w + suf[i] > w) { // printf("%d: %d %d %d %d %d bo %d\n", a[j].ind, a[j].w, a[j].xstart, a[j].xstop, suf[i], w, sufind[i]); return 0; } temp[b++] = a[j++]; } } for (int i=p; i<=q; i++) a[i] = temp[i]; return 1; } int main() { int z; SC(z); while(z--) { int n; SC2(n, w); REP(i, n) { int x1, y1, x2, y2; SC2(x1, y1); SC2(x2, y2); a[i].w = abs(y1 - y2); a[i].xstart = min(x1, x2); a[i].ind = i; } REP(i, n) { int x1, y1, x2, y2; SC2(x1, y1); SC2(x2, y2); a[i].xstop = min(x1, x2); } sort(a, a+n, [](car c, car d) { return c.xstart < d.xstart; }); if(mergesort(0, n-1)) printf("TAK\n"); else printf("NIE\n"); } return 0; } |