Submission #1305126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305126		Johan	Arranging Shoes (IOI19_shoes)	C++20	85 / 100	1110 ms	352952 KiB

shoes

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
const int B = 1e5;
int len, cnt[450][B * 2 + 2];
deque < int > b[450];
void upd(int l, int r){
    int ll = l / len, rr = r / len;

    // Eyni blokdursa (dəyişmir)
    if(ll == rr){
        deque<int> d;
        for(int i = l % len; i <= r % len; i++)
            d.push_back(b[ll][i]);
        d.push_front(d.back());
        d.pop_back();
        int idx = 0;
        for(int i = l % len; i <= r % len; i++)
            b[ll][i] = d[idx++];
        return;
    }

    // ---- ll bloku (sondan sağa sürüşdürmə) ----
    int take = b[rr][r % len];

    for(int i = l % len; i < len; i++){
        swap(take, b[ll][i]);
    }

    int lst = take;
    cnt[ll][b[ll][l % len] + B]++;
    cnt[ll][lst + B]--;

    // ---- orta bloklar (dəyişmir) ----
    for(int i = ll + 1; i <= rr - 1; i++){
        b[i].push_front(lst);
        cnt[i][lst + B]++;
        lst = b[i].back();
        b[i].pop_back();
        cnt[i][lst + B]--;
    }

    // ---- rr bloku (əvvəldən sağa sürüşdürmə) ----
    take = lst;

    for(int i = 0; i <= r % len; i++){
        swap(take, b[rr][i]);
    }

    cnt[rr][lst + B]++;
    cnt[rr][take + B]--;
}

int ask(int l, int r, int x){
	int ll = l / len, rr = r / len;
//	cout << l << '-' << r << "<->" << ll << '-' << rr << endl;
	if(ll == rr){
		for(int i = l % len; i <= r % len; i++){
			if(b[ll][i] == x){
				return ll * len + i;
			}
		}
		return l;
	}
	for(int i = l % len; i < len; i++){
		if(b[ll][i] == x){
			return ll * len + i;
		}
	}
//	cout << "sonraki: ";
//	for(auto i : b[ll + 1])cout << i << '-';cout << endl;
//	cout << "dasssaqq: " << cnt[ll + 1][-9] << endl;
	int idx = -1;
	for(int i = ll + 1; i <= rr; i++){
		if(cnt[i][x + B] > 0){
			idx = i;
			break;
		}
	}
	if(idx != -1){
		for(int i = 0; i < len; i++){
			if(b[idx][i] == x){
				return idx * len + i;
			}
		}
	}
	for(int i = 0; i <= r % len; i++){
		if(b[rr][i] == x){
			return rr * len + i;
		}
	}
	return l;
}
long long count_swaps(vector < int > s){
	int n = s.size();
	len = sqrt(n + .0) + 1;
	for(int i = 0; i < n; i++){
		b[i / len].push_back(s[i]);
		cnt[i / len][s[i] + B]++;
	}
	long long ans = 0;
	for(int i = 0; i < n; i++){
		int si = b[i / len][i % len], si_ = si;
		if(i >= 1)
			si_ = b[(i - 1) / len][(i - 1) % len];
		if(si > 0 && i % 2 == 0){
			int j = ask(i, n - 1, -si);
			ans += (j - (i + 1) + 1);
//			cout << i << '-' << j << "--" << si << endl;
			upd(i, j);
		}
		else if(si < 0 && i % 2 == 1 || si > 0 && si != -si_){
			int j = ask(i, n - 1, -si_);
			ans += (j - (i + 1) + 1);
//			cout << i << '-' << j << endl;
			upd(i, j);
		}
//		for(int _ = 0; _ < len; _++){
//			for(auto __ : b[_])cout << __ << ' ';
//		}
//		cout << endl;
	}
	return ans;
}
/*
4
-6 9 -9 6 7 -6 6 -7
*/

Compilation message (stderr)

shoes.cpp:20:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   20 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
shoes.cpp:27:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   27 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
shoes.cpp:29:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   29 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
shoes.cpp:43:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   43 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
In file included from shoes.cpp:46:
shoes.h:7:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
    7 | long long count_swaps(std::vector<int> S);
      |                                         ^
shoes.h:7:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
shoes.h:7:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
shoes.h:7:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
shoes.h:7:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
shoes.h:7:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
shoes.h:7:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
shoes.h:7:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
shoes.cpp:53:22: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   53 | void upd(int l, int r){
      |                      ^
shoes.cpp:53:22: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
shoes.cpp:53:22: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
shoes.cpp:53:22: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
shoes.cpp:100:28: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  100 | int ask(int l, int r, int x){
      |                            ^
shoes.cpp:100:28: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
shoes.cpp:100:28: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
shoes.cpp:100:28: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
shoes.cpp:140:39: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  140 | long long count_swaps(vector < int > s){
      |                                       ^
shoes.cpp:140:39: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
shoes.cpp:140:39: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
shoes.cpp:140:39: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

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