From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
Date: Tue, 5 Oct 2021 21:49:54 +0200
Subject: Duzy commit ze smieciami

---
 Semestr 4/aisd/pracownia4/brut.cpp         |  69 -------------
 Semestr 4/aisd/pracownia4/gen.py           |  24 -----
 Semestr 4/aisd/pracownia4/rozw.cpp         | 157 -----------------------------
 Semestr 4/aisd/pracownia4/rozw2.cpp        | 135 -------------------------
 Semestr 4/aisd/pracownia4/rozw3.cpp        | 149 ---------------------------
 Semestr 4/aisd/pracownia4/show_problem.pdf | Bin 61345 -> 0 bytes
 Semestr 4/aisd/pracownia4/test.sh          |  21 ----
 7 files changed, 555 deletions(-)
 delete mode 100644 Semestr 4/aisd/pracownia4/brut.cpp
 delete mode 100644 Semestr 4/aisd/pracownia4/gen.py
 delete mode 100644 Semestr 4/aisd/pracownia4/rozw.cpp
 delete mode 100644 Semestr 4/aisd/pracownia4/rozw2.cpp
 delete mode 100644 Semestr 4/aisd/pracownia4/rozw3.cpp
 delete mode 100644 Semestr 4/aisd/pracownia4/show_problem.pdf
 delete mode 100755 Semestr 4/aisd/pracownia4/test.sh

(limited to 'Semestr 4/aisd/pracownia4')

diff --git a/Semestr 4/aisd/pracownia4/brut.cpp b/Semestr 4/aisd/pracownia4/brut.cpp
deleted file mode 100644
index 32f4ebb..0000000
--- a/Semestr 4/aisd/pracownia4/brut.cpp	
+++ /dev/null
@@ -1,69 +0,0 @@
-#include <bits/stdc++.h>
-using namespace std;
-typedef long long ll;
-
-struct insert_list {
-    vector<int> v;
-    
-    insert_list() {
-    }
-
-    void insert(int p, int val) {
-        assert(p <= v.size());
-        assert(p >= 0);
-        vector<int> temp;
-        for (int i = 0; i < p; i++) {
-            temp.push_back(v[i]);
-        }
-        temp.push_back(val);
-        for (int i = p; i < v.size(); i++) {
-            temp.push_back(v[i]);
-        }
-        v = temp;
-    }
-
-    void erase(int p) {
-        assert(p <= v.size());
-        assert(p >= 1);
-        vector<int> temp;
-        for (int i = 0; i < p-1; i++) {
-            temp.push_back(v[i]);
-        }
-        for (int i = p; i < v.size(); i++) {
-            temp.push_back(v[i]);
-        }
-        v = temp;
-    }
-
-    ll sum(int l, int r) {
-        ll ans = 0;
-        for (int i = l-1; i < r; i++) {
-            ans += v[i];
-        }
-        return ans;
-    }
-};  
-
-insert_list v;
-
-int main() {
-    ios_base::sync_with_stdio(false);
-    cin.tie();
-    int n;
-    cin >> n;
-    for (int i = 0; i < n; i++) {
-        char c;
-        cin >> c;
-        if (c == 'D') {
-            int a;
-            cin >> a;
-            v.erase(a);
-        }
-        else {
-            int a, b;
-            cin >> a >> b;
-            if (c == 'I') v.insert(a, b);
-            else cout << v.sum(a,b) << "\n";
-        }
-    }
-}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia4/gen.py b/Semestr 4/aisd/pracownia4/gen.py
deleted file mode 100644
index 733a60e..0000000
--- a/Semestr 4/aisd/pracownia4/gen.py	
+++ /dev/null
@@ -1,24 +0,0 @@
-from random import randint, seed, choice
-import sys
-
-
-seed(sys.argv[1])
-n = int(sys.argv[2])
-l = 0
-print(n)
-
-
-for i in range(n):
-    c = choice('ISD')
-    if l == 0:
-        c = 'I'
-
-    if c == 'D':
-        print(c, randint(1, l))
-        l -= 1
-    elif c == 'I':
-        print(c, randint(0, l), randint(-10, 10))
-        l += 1
-    else:
-        a = randint(1, l)
-        print(c, a, randint(a, l))
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia4/rozw.cpp b/Semestr 4/aisd/pracownia4/rozw.cpp
deleted file mode 100644
index 9c314e2..0000000
--- a/Semestr 4/aisd/pracownia4/rozw.cpp	
+++ /dev/null
@@ -1,157 +0,0 @@
-#include <bits/stdc++.h>
-using namespace std;
-typedef long long ll;
-
-const int K = 20;
-const int M = (1<<K);
-const size_t tree_size = M*2 + 10;
-
-struct query {
-    char type;
-    union {
-        struct insert {
-            int p;
-            int x;
-        } insert;
-        struct sum {
-            int from;
-            int to;
-        } sum;
-        int del;
-    } info;
-};
-
-struct kox_set {
-    ll tree[tree_size];
-
-    kox_set() {
-        for (int i = 0; i < tree_size; i++) tree[i] = 0;
-    }
-
-    void add(int val) {
-        update(val, 1);
-    }
-
-    void del(int val) {
-        update(val, -1);
-    }
-
-    void update(int where, int val) {
-        where += M;
-        while (where) {
-            tree[where] += val;
-            where /= 2;
-        }
-    }
-
-    ll sum(int from, int to) {
-        from += M;
-        to += M;
-        ll ans = tree[from];
-        if (from != to) ans += tree[to];
-        while (from/2 != to/2) {
-            if (from % 2 == 0)  ans += tree[from + 1];
-            if (to % 2 == 1)    ans += tree[to - 1];
-            to /= 2; from /= 2;
-        }
-        return ans;
-    }
-
-    int kth_elem(int k) {
-        int where = 1;
-        while (where < M) {
-            where *= 2;
-            if (tree[where] < k) {
-                k -= tree[where];
-                where += 1;
-            } 
-        }
-        return where - M;
-    }
-
-    void fill(int value) {
-        for (int i = 0; i < M; i++) {
-            tree[i + M] = value;
-        }
-        for (int d = K-1; d >= 0; d--) {
-            int maks = (1<<d);
-            for (int i = 0; i < maks; i++) {
-                int ind = i + maks;
-                tree[ind] = tree[ind*2] + tree[ind*2 + 1];
-            }
-        }
-    }
-};
-
-vector<query> queries;
-map<int, int> q_to_pos;
-kox_set secik;
-kox_set pstree;
-
-
-int main() {
-    int n, inserts = 0;
-    scanf("%d", &n);
-    for (int i = 0; i < n; ++i) {
-        char c;
-        scanf(" %c", &c);
-        query q;
-        q.type = c;
-        if (c == 'D') {
-            int a;
-            scanf("%d", &a);
-            pstree.add(a);
-            q.info.del = a;
-        }
-        else {
-            int a, b;
-            scanf("%d%d", &a, &b);
-            q.type = c;
-            if (c == 'I') {
-                q.info.insert = {a, b};
-                inserts++;
-            } else {
-                q.info.sum = {a, b};
-            }
-        }
-        queries.push_back(q);
-    }
-
-    secik.fill(1);
-    for (int i = n-1; i >= 0; i--) {
-        query q = queries[i];
-        if (q.type == 'D') {
-            pstree.del(q.info.del);
-        }
-        if (q.type == 'I') {
-            int offset = pstree.sum(0, q.info.insert.p);
-            int kth = secik.kth_elem(q.info.insert.p + offset + 1);
-            secik.del(kth);
-            q_to_pos[i] = kth;
-            cout << q.info.insert.p << " " << offset << "\n";
-            cout << i << ": " << q_to_pos[i] << "\n";
-        }
-    }
-    secik.fill(0);
-    pstree.fill(0);
-
-    for (int i = 0; i < n; i++) {
-        query q = queries[i];
-        if (q.type == 'I') {
-            secik.add(q_to_pos[i]);
-            pstree.update(q_to_pos[i], q.info.insert.x);
-            // cout << "Inserting " << q.info.insert.x << " to " << q_to_pos[i] << "\n";
-        }
-        if (q.type == 'D') {
-            int pos = secik.kth_elem(q.info.del);
-            // cout << "kth: " << q.info.del << " " << pos << "\n";
-            secik.del(pos);
-            pstree.update(pos, -pstree.tree[pos + M]);
-        }
-        if (q.type == 'S') {
-            int from = secik.kth_elem(q.info.sum.from);
-            int to = secik.kth_elem(q.info.sum.to);
-            printf("%lld\n", pstree.sum(from, to));
-        }   
-    }
-}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia4/rozw2.cpp b/Semestr 4/aisd/pracownia4/rozw2.cpp
deleted file mode 100644
index 17562a9..0000000
--- a/Semestr 4/aisd/pracownia4/rozw2.cpp	
+++ /dev/null
@@ -1,135 +0,0 @@
-#include <bits/stdc++.h>
-using namespace std;
-
-struct treap {
-    typedef long long T;
-    treap *left = nullptr;
-    treap *right = nullptr;
-    int rank, items = 1;
-    T value;
-    T sum;
-    bool rev = false;
-
-    treap(T val = T()) : rank(rand()), value(val), sum(val) {}
-
-    inline void update() {
-        if (rev) {
-            swap(left, right);
-            if (left)   left->rev   = !left->rev;
-            if (right)  right->rev  = !right->rev;
-            rev = false;
-        }
-    }
-};
-
-inline int items(treap *t) { return t ? t->items : 0; }
-inline int sum(treap *t)   { return t ? t->sum : 0; }
-inline void recalc(treap *t) { 
-    t->items = items(t->left) + items(t->right) + 1; 
-    t->sum   = sum(t->left) + sum(t->right) + t->value;
-}
-
-pair<treap*, treap*> split(treap *t, int k) {
-    if (!t) return {nullptr, nullptr};
-    t->update();
-    if (items(t->left) < k) {
-        auto p = split(t->right, k - items(t->left) - 1);
-        t->right = p.first;
-        recalc(t);
-        return {t, p.second};
-    }
-    else {
-        auto p = split(t->left, k);
-        t->right = p.first;
-        recalc(t);
-        return {p.first, t};
-    }
-}
-
-treap* merge(treap *a, treap *b) {
-    if (!a) return b;
-    if (!b) return a;
-    a->update();
-    b->update();
-    if (a->rank > b->rank) {
-        a->right = merge(a->right, b);
-        recalc(a);
-        return a;
-    }
-    else {
-        b->left = merge(a, b->left);
-        recalc(b);
-        return b;
-    }
-}
-
-treap::T select(treap *t, int k) {
-    if (!t) return treap::T();
-    t->update();
-    int i = items(t->left);
-    if (i == k)         return t->value;
-    else if (i > k)     return select(t->left, k);
-    else                return select(t->right, k - i - 1);
-}
-
-treap *insert (treap *t, treap::T val, int k) {
-    auto p = split(t, k);
-    return merge(merge(p.first, new treap(val)), p.second);
-}
-
-treap *erase(treap *t, int k) {
-    auto p1 = split(t, k);
-    auto p2 = split(p1.second, 1);
-    return merge(p1.first, p2.second);
-}
-
-treap::T sum(treap *t, int l, int r) {
-    auto p1 = split(t, r);
-    auto p2 = split(p1.first, l);
-    return sum(p2.second);
-} 
-
-void write(treap *t) {
-    if (!t) return;
-    t->update();
-    write(t->left);
-    cout << t->value << " ";
-    write(t->right);
-}
-void destroy(treap *t) {
-    if (!t) return;
-    destroy(t->left);
-    destroy(t->right);
-    delete t;
-}
-
-treap *t = 0;
-
-int main() {
-    int n;
-    scanf("%d", &n);
-    for (int i = 0; i < n; i++) {
-        char c;
-        scanf(" %c", &c);
-        if (c == 'I') {
-            int p, x;
-            scanf("%d%d", &p, &x);
-            t = insert(t, x, p);
-        }
-        if (c == 'D') {
-            int p;
-            scanf("%d", &p);
-            t = erase(t, p - 1);
-        }
-        if (c == 'S') {
-            int l, r;
-            scanf("%d%d", &l, &r);
-            printf("ans: %lld\n", sum(t, l, r));
-        }
-        cout << "Treap:\n";
-        write(t);
-        cout << "\n";
-    }
-
-    destroy(t);
-}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia4/rozw3.cpp b/Semestr 4/aisd/pracownia4/rozw3.cpp
deleted file mode 100644
index ec107ef..0000000
--- a/Semestr 4/aisd/pracownia4/rozw3.cpp	
+++ /dev/null
@@ -1,149 +0,0 @@
-
-#include <bits/stdc++.h>
-using namespace std;
-
-struct treap
-{
-    typedef long long T;
-    treap *left = nullptr, *right = nullptr;
-    
-    int rank, items = 1;
-    bool rev = false;
-    T value, sum;
-    
-    treap(T val = T()) : value(val), sum(val), rank(rand()) { }
-    
-    inline void update()
-    {
-        if(rev)
-        {
-            swap(left, right);
-            if(left) left->rev = !left->rev;
-            if(right) right->rev = !right->rev;
-            rev = false;
-        }
-    }
-};
-
-inline int items(treap *t) { return t ? t->items : 0; }
-inline treap::T sum(treap *t) { return t ? t->sum : 0; }
-inline void recalc(treap *t) { 
-    t->items = items(t->left) + items(t->right) + 1; 
-    t->sum   = sum(t->left) + sum(t->right) + t->value;    
-}
-
-pair<treap*, treap*> split(treap *t, int k) //dzieli na prefiks dlugosci k i reszte
-{
-    if(!t) return make_pair(nullptr, nullptr);
-    //t = new treap(*t); //odkomentowac zeby zrobic strukture trwala
-    t->update();
-    if(items(t->left) < k)
-    {
-        auto p = split(t->right, k - items(t->left) - 1);
-        t->right = p.first;
-        recalc(t);
-        return make_pair(t, p.second);
-    }
-    else
-    {
-        auto p = split(t->left, k);
-        t->left = p.second;
-        recalc(t);
-        return make_pair(p.first, t);
-    }
-}
-
-treap* merge(treap *a, treap *b)
-{
-    if(!a) return b;
-    if(!b) return a;
-    a->update();
-    b->update();
-    if(a->rank > b->rank) {
-        a->right = merge(a->right, b);
-        recalc(a);
-        return a;
-    }
-    else {
-        b->left = merge(a, b->left);
-        recalc(b);
-        return b;
-    }
-}
-
-treap::T select(treap *t, int k) //zwraca k-ty element
-{
-    if(!t) return treap::T();
-    t->update();
-    int i = items(t->left);
-    if(i == k) return t->value;
-    if(i > k) return select(t->left, k);
-    return select(t->right, k - i - 1);
-}
-
-treap* insert(treap *t, treap::T val, int k) //wstaw val na pozycje k (liczac od 0)
-{
-    auto p = split(t, k);
-    return merge(merge(p.first, new treap(val)), p.second);
-}
-void write(treap *t)
-{
-    if(!t) return;
-    t->update();
-    write(t->left);
-    cout << "(" << t->value << ", " << t->sum << ") ";
-    write(t->right);
-}
-
-treap* erase(treap *t, int k)
-{
-    auto p1 = split(t, k);
-    auto p2 = split(p1.second, 1);
-    return merge(p1.first, p2.second);
-}
-
-treap* reverse(treap *t, int a, int b) //odwroc przedzial <a, b)
-{
-    auto p1 = split(t, b);
-    auto p2 = split(p1.first, a);
-    if(p2.second) p2.second->rev = !p2.second->rev;
-    return merge(merge(p2.first, p2.second), p1.second);
-}
-
-treap::T sum(treap* t, int l, int r) {
-    auto p1 = split(t, r);
-    auto p2 = split(p1.first, l);
-    treap::T ret = sum(p2.second);
-    merge(merge(p2.first, p2.second), p1.second);
-    return ret;
-}
-
-treap *root = 0;
-
-int main() {
-    int n;
-    scanf("%d", &n);
-    for (int i = 0; i < n; i++) {
-        char c;
-        scanf(" %c", &c);
-        if (c == 'I') {
-            int p, x;
-            scanf("%d%d", &p, &x);
-            root = insert(root, x, p);
-        }
-        if (c == 'D') {
-            int p;
-            scanf("%d", &p);
-            root = erase(root, p - 1);
-        }
-        if (c == 'S') {
-            int l, r;
-            scanf("%d%d", &l, &r);
-            printf("%lld\n", sum(root, l - 1, r));
-        }
-        // cout << "Treap:\n";
-        // write(root);
-        // cout << "\n";
-    }
-
-}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia4/show_problem.pdf b/Semestr 4/aisd/pracownia4/show_problem.pdf
deleted file mode 100644
index 8a1c155..0000000
Binary files a/Semestr 4/aisd/pracownia4/show_problem.pdf and /dev/null differ
diff --git a/Semestr 4/aisd/pracownia4/test.sh b/Semestr 4/aisd/pracownia4/test.sh
deleted file mode 100755
index dc725ad..0000000
--- a/Semestr 4/aisd/pracownia4/test.sh	
+++ /dev/null
@@ -1,21 +0,0 @@
-#!/bin/bash
-
-make brut
-make rozw3
-
-
-for i in {1..10000}
-do
-    echo $i
-    python3 gen.py $i $1 > test.in
-    ./rozw3 < test.in > wa.out
-    ./brut < test.in > test.out
-
-    if diff -w test.out wa.out
-    then
-        echo ok
-    else
-        echo nieok
-        break
-    fi
-done
-- 
cgit v1.2.3