Submission #385021

#	Time	Username	Problem	Language	Result	Execution time	Memory
385021		thiago4532	Teams (IOI15_teams)	C++17	34 / 100	4081 ms	335212 KiB

teams

#define _FORTIFY_SOURCE 0 
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
#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 "teams.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
 
using namespace std;
typedef pair<int, int> pii;
const int maxn = 5e5 + 10;
const int maxq = 2e5 + 10;
pii v[maxn];
int n;
 
struct node {
    node *l, *r;
    int v;
    node () {
        l = r = nullptr;
        v = 0;
    }
};
 
inline int val(node *t) {
    if (t != nullptr) return t->v;
    return 0;
}
 
inline node* l(node* t) {
    return t ? t->l : nullptr;
}
 
inline node* r(node *t ) {
    return t ? t->r : nullptr;
}
 
inline int valor(node *t) {
    return t ? t->v : 0;
}
 
void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
    if (ini == fim) {
        no->v = valor(old) + v;
        return;
    }
 
    int meio = (ini + fim) >> 1;
 
    if (p <= meio) {
        if (old == nullptr || old->l == nullptr) no->l = new node;
        else no->l = new node(*old->l);
 
        if(old != nullptr && old->r != nullptr) no->r = old->r;
 
        update(l(old), no->l, p, v, ini, meio);
    }else {
        if (old == nullptr || old->r == nullptr) no->r = new node;
        else no->r = new node(*old->r);
 
        if(old != nullptr && old->l != nullptr) no->l = old->l;
 
        update(r(old), no->r, p, v, meio+1, fim);
    }
 
    no->v = val(no->l) + val(no->r);
}
 
int query(node *no, int l, int r, int ini=1, int fim=n) {
    if(no == nullptr || ini > r || fim < l) return 0;
    l = max(l, ini);
    r = min(r, fim);
    if(l <= ini && fim <= r) return no->v;
 
    int meio = (ini + fim) >> 1;
 
    int p1 = query(no->l, l, r, ini, meio);
    int p2 = query(no->r, l, r, meio+1, fim);
    return p1 + p2;
}
node* version[maxn];
int nv, ver[maxn];
 
void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 1; i <= n; i++)
        v[i] = {A[i-1], B[i-1]};
 
    sort(v+1, v+n+1);
 
    int last = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i].ff != last) {
            ver[last] = nv;
            last = v[i].ff;
        }
 
        version[++nv] = new node;
        update(version[nv-1], version[nv], v[i].ss, 1);
    }
    ver[last] = nv;
    for (int i = 1; i <= n; i++)
        ver[i] = max(ver[i-1], ver[i]);
    //cout << "OI " << nv << '\n';
    //for (int i = 1; i <= n; i++)
        //cout << ver[i] << " \n"[i==nv];
}
int qtd[maxn];
typedef long long ll;
ll dp[maxn];
int freq[maxn];

int lc=-1, inic=-1, fimc=-1;
ll cache;
inline ll solve(int l, int r, int ini, int fim) {
    if (l != lc || ini != inic || fim != fimc) {
        lc = l, inic = ini, fimc = fim;
        cache = query(version[ ver[l] ], ini, fim);
    }
    return query(version[ ver[r] ], ini, fim) - cache;
}
 
int can(int M, int K[]) {
    static vector<int> q;
    q.clear();
    ll sum = 0;
    for (int i = 0; i < M; i++) 
        q.push_back(K[i]), sum += K[i];
    if (sum > n) return 0;
    for (auto& e : q)
        freq[e]++;
 
    sort(q.begin(), q.end());
    q.erase(unique(q.begin(), q.end()), q.end());
 
    bool certo = true;
    int m = (int)q.size(); // m < sqrt(M)
    for (int i = 0; i < m; i++) {
        ll f = 1ll*freq[q[i]]*q[i]; // numero de caras na esquerda
        dp[i] = solve(0, q[i], q[i], n) - f;
 
        for (int j = 0; j < i; j++)
            dp[i] = min(dp[i], dp[j] + solve(q[j], q[i], q[i], n) - f);
 
        if (dp[i] < 0) { // vizinhanca menor que 0
            certo = false;
            break;
        }
    }
 
    for (int i = 0; i < m; i++)
        dp[i] = 0;
    for (auto& e : q)
        freq[e] = 0;
 
    return certo;
}
 
// matching perfeito ( teorema de hall )
// S(vizinhanca de A) >= S(A) para todo o subset

Compilation message (stderr)

teams.cpp:1: warning: "_FORTIFY_SOURCE" redefined
    1 | #define _FORTIFY_SOURCE 0
      | 
<built-in>: note: this is the location of the previous definition
teams.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   25 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
teams.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
teams.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
teams.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   48 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
In file included from teams.cpp:51:
teams.h:4:34: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
    4 | void init(int N, int A[], int B[]);
      |                                  ^
teams.h:4:34: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.h:4:34: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.h:4:34: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.h:4:34: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
teams.h:4:34: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.h:4:34: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.h:4:34: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.h:5:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
    5 | int can(int M, int K[]);
      |                       ^
teams.h:5:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.h:5:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.h:5:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.h:5:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
teams.h:5:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.h:5:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.h:5:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:66:11: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   66 |     node () {
      |           ^
teams.cpp:66:11: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:66:11: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:66:11: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:72:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   72 | inline int val(node *t) {
      |                       ^
teams.cpp:72:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:72:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:72:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:77:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   77 | inline node* l(node* t) {
      |                       ^
teams.cpp:77:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:77:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:77:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:81:24: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   81 | inline node* r(node *t ) {
      |                        ^
teams.cpp:81:24: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:81:24: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:81:24: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:85:25: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   85 | inline int valor(node *t) {
      |                         ^
teams.cpp:85:25: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:85:25: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:85:25: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:89:68: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   89 | void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
      |                                                                    ^
teams.cpp:89:68: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:89:68: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:89:68: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp: In function 'void update(node*, node*, int, int, int, int)':
teams.cpp:89:68: warning: declaration of 'v' shadows a global declaration [-Wshadow]
teams.cpp:60:5: note: shadowed declaration is here
   60 | pii v[maxn];
      |     ^
teams.cpp: At global scope:
teams.cpp:116:55: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  116 | int query(node *no, int l, int r, int ini=1, int fim=n) {
      |                                                       ^
teams.cpp:116:55: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:116:55: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:116:55: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:131:34: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  131 | void init(int N, int A[], int B[]) {
      |                                  ^
teams.cpp:131:34: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:131:34: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:131:34: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:162:47: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  162 | inline ll solve(int l, int r, int ini, int fim) {
      |                                               ^
teams.cpp:162:47: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:162:47: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:162:47: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teams.cpp:170:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  170 | int can(int M, int K[]) {
      |                       ^
teams.cpp:170:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teams.cpp:170:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teams.cpp:170:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23