/ Randle /

记录详情

Time Exceeded


  
# 状态 耗时 内存占用
#1 Time Exceeded ≥1006ms ≥25.125 MiB
#2 Time Exceeded ≥1004ms ≥23.465 MiB
#3 Time Exceeded ≥1007ms ≥23.625 MiB
#4 Time Exceeded ≥1008ms ≥24.043 MiB
#5 Time Exceeded ≥1006ms ≥23.594 MiB
#6 Time Exceeded ≥1004ms ≥24.816 MiB
#7 Time Exceeded ≥1006ms ≥24.875 MiB
#8 Time Exceeded ≥1003ms ≥24.875 MiB
#9 Time Exceeded ≥1002ms ≥27.219 MiB
#10 Time Exceeded ≥1003ms ≥25.094 MiB

代码

#include<bits/stdc++.h>

#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b

using namespace std;

const int maxn=1e6+7;

inline int read()
{
    int k=0;
    int f=1;
    char c=getchar();
    while(c>'9'||c<'0') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0') {
        k=k*10+c-'0';
        c=getchar();
    }
    return f*k;
}

struct Node
{
    int to;
    int next;
    int w;
}node[maxn];

int head[maxn];
int qboy[maxn],qgirl[maxn],boy[maxn],girl[maxn],three[maxn];//exboy和exgirl表示男孩女孩对暗恋者的期望值。boy和girl分别指这个男女生现任女男友,three是女生离做小三的距离,也就是要被某个男生作为首选,最少还差多少与他的倾心值
bool usedb[maxn],usedg[maxn];
int n;

inline bool find(int x)
{
    usedb[x]=true;
    int side=head[x];
    while(side!=-1) {
        if(usedg[node[side].to]==false) {
             if(qboy[x]+qgirl[node[side].to]==node[side].w) {
                 usedg[node[side].to]=true;
                 if(girl[node[side].to]==false||find(girl[node[side].to])) {
                      girl[node[side].to]=x;
                      boy[x]=node[side].to;
                      return true;
                 }
             }
             else {
                three[node[side].to]=min(three[node[side].to],qboy[node[side].to]+qgirl[node[side].w]);
             }
         }
         side=node[side].next;
    }
    return false;
}

inline void solve()
{
    for(int i=1;i<=n;++i) {
        memset(three,0x7f,sizeof(three));
        while(true) {
           memset(usedg,false,sizeof(usedg));
           memset(usedb,false,sizeof(usedb));
           if(find(i)) break;
           int minus=three[0];
           for(int j=1;j<32;++j) {
               if(usedg[j]==false)
                     minus=min(three[j],minus);
           }
           if(minus==three[0]) break;
           for(int j=i;j<=n;++j)
               if(usedb[j])
                   qboy[j]-=minus;
           for(int j=1;j<32;++j)
               if(usedg[j])
                   qgirl[j]+=minus;   
        }
    }
}

int tot=0;

inline void add(int u,int v,int w)
{
    node[++tot].next=head[u];
    node[tot].to=v;
    node[u].next=tot;
    node[tot].w=w;
    qboy[u]=max(qboy[u],w);
}

int main()
{
    memset(qboy,0,sizeof(qboy));
    memset(qgirl,0,sizeof(qgirl));
    memset(girl,0,sizeof(girl));
    memset(boy,0,sizeof(boy));
    n=read();
    for(int i=1;i<=n;++i) {
         int k=read();
         for(int j=1;j<32;++j) {
            if((1<<(j-1))&k)
                add(i,j,1<<(j-1));
         }
    }
    solve();
    int ans=0;
    for(int i=1;i<=n;++i) {
         if(boy[i]) ans+=1<<(boy[i]-1);
         else ans^=1;
    }
    printf("%d\n",ans);
    return 0;
}

信息

递交者
类型
递交
题目
奇数异或(国家集训队)
题目数据
下载
语言
C++
递交时间
2017-11-08 20:30:44
评测时间
2017-11-08 20:30:44
评测机
分数
0
总耗时
≥10054ms
峰值内存
≥27.219 MiB