Submission #468994

#	Time	Username	Problem	Language	Result	Execution time	Memory
468994		Cross_Ratio	Arranging Shoes (IOI19_shoes)	C++14	85 / 100	115 ms	73880 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
 
 
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        int i;
        for(i=MAX/2-1;i>=1;i--) {
            seg[i] = seg[2*i] + seg[2*i+1];
        }
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
    }
    int sum(int s, int e) {
        return sum(s, e, 1, 0, MAX/2);
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = seg[2*n] + seg[2*n+1];
            n /= 2;
        }
    }
    void Minus(int n) {
        seg[n+MAX/2]--;
        update(n);
    }
};
typedef pair<int,int> P;
vector<deque<int> > adj;
P pt[200005];
bool vis[200005];
long long count_swaps(vector<int> S) {
    int N = S.size();
    N /= 2;
    adj.resize(N);
    int i, j;
    for(i=0;i< 2*N; i++) {
        if(S[i] > 0) adj[S[i]-1].push_back(i);
    }
    int cnt = 0;
    SegTree tree(2*N + 5);
    for(i=0;i<2*N;i++) {
        if(S[i] < 0) {
            int d = adj[-S[i]-1].front();
            adj[-S[i]-1].pop_front();
            pt[cnt].first = i;
            pt[cnt].second = d;
            cnt++;
        }
    }
    long long int ans = 0;
    for(i=0;i<N;i++) {
        int mi = 1e9;
        int a, b, c;
        j = i;
        //for(j=0;j<N;j++) {
            if(!vis[j]) {
                cnt = pt[j].first + pt[j].second;
                cnt += tree.sum(0, pt[j].first) + tree.sum(0, pt[j].second);
                if(pt[j].first < pt[j].second) cnt--;
                if(cnt < mi) {
                    mi = cnt;
                    a = pt[j].first;
                    b = pt[j].second;
                    c = j;
                }
            }
        //}
        //cout << mi << ' ';
        if(N <= 1000) {
          for(j=0;j<N;j++) {
            if(!vis[j]) {
                cnt = pt[j].first + pt[j].second;
                cnt += tree.sum(0, pt[j].first) + tree.sum(0, pt[j].second);
                if(pt[j].first < pt[j].second) cnt--;
                if(cnt < mi) {
                    mi = cnt;
                    a = pt[j].first;
                    b = pt[j].second;
                    c = j;
                }
            }
        }
        }
        //cout << mi << ' ';
        vis[c] = true;
        tree.Minus(a);
        tree.Minus(b);
        ans += mi;
    }
    return ans;
}
 

Compilation message (stderr)

shoes.cpp: In member function 'int SegTree::sum(int, int, int, int, int)':
shoes.cpp:24:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:101:16: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |         vis[c] = true;
      |         ~~~~~~~^~~~~~
shoes.cpp:31:11: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |         n += MAX/2;
      |         ~~^~~~~~~~
shoes.cpp:69:16: note: 'b' was declared here
   69 |         int a, b, c;
      |                ^
shoes.cpp:39:14: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |         seg[n+MAX/2]--;
      |             ~^~~~~~
shoes.cpp:69:13: note: 'a' was declared here
   69 |         int a, b, c;
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15