QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#46635#1173. Knowledge Is...gs22059test#WA 10ms29160kbC++9.6kb2022-08-30 16:22:192022-08-30 16:22:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-30 16:22:21]
  • 评测
  • 测评结果：WA
  • 用时：10ms
  • 内存：29160kb
查看
  • [2022-08-30 16:22:19]
  • 提交

answer

#include<bits/stdc++.h> // header
using namespace std; // std function
#define int long long
#define elif else if // redirect
#define fall(x) (x).begin(), (x).end() // macro
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) // macro
// struct
struct cliques{int loc,lr,i;};
struct tasks{int l,r,idx;};
struct pq_comp{bool operator()(pair<int,int> a, pair<int,int> b){return a.first>b.first;}};
// comparators
bool fmq_comp(const cliques a, const cliques b){
    if(a.loc!=b.loc)return a.loc<b.loc;
    return a.lr<b.lr;
}
bool col_comp(const tasks a, const tasks b){return a.l<b.l;}
bool col_reset_comp(const tasks a, const tasks b){return a.idx<b.idx;}
bool align_right_normal(const tasks a, const tasks b){return a.r<b.r;}
bool align_left_normal(const tasks a, const tasks b){return a.l<b.l;}
bool align_right_inverse(const tasks a, const tasks b){return a.r>b.r;}
bool align_left_inverse(const tasks a, const tasks b){return a.l>b.l;}
// variable declarations
vector<int> maximum_clique, non_maximum_clique, max_left, max_right;
vector<tasks> task_list;
vector<cliques> fmq_list; // 최대 클리크 찾기용 누적합
priority_queue<pair<int, int>, vector<pair<int, int>>, pq_comp> color_last; // 색상별 구간 중 가장 오른쪽 위치
vector<pair<int, int>> bipartite_matches; // 이분 매칭 리스트
vector<tasks> list_max, list_max_left, list_max_right;
set<int> colors[400000]; // 색상별 정점 리스트
int m,n,l[400000],r[400000]; // 입력
int bipartite_match_idx[400000]; // 이분 매칭한 게 있는 경우 해당 정점의 인덱스, 아니면 -1
int task_color[400000]; // 정점 색상
int color_count[400000]; // 색상별 정점 수
int workers[400000]; // 작업 매칭
// function declarations
void init(){ // 초기화 및 입력
    memset(bipartite_match_idx,-1,sizeof(bipartite_match_idx));
    memset(workers,-1,sizeof(workers));
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>l[i]>>r[i];
        task_list.push_back({l[i],r[i],i});
    }
}

void find_maximum_clique(){ // 최대 클리크 찾아서 원소 저장, 최대 클리크 아닌 것은 따로 저장
    int i,max_location=0, max_number=0,a=0;
    for(i=0;i<(int)task_list.size();i++){
        fmq_list.push_back({task_list[i].l,1,i});
        fmq_list.push_back({task_list[i].r+1,-1,i});
    }
    sort(fall(fmq_list),fmq_comp);
    for(i=0;i<(int)fmq_list.size();i++){
        a+=fmq_list[i].lr;
        if(a>max_number){
            max_number=a;
            max_location=fmq_list[i].loc;
        }
    }
    for(i=0;i<(int)task_list.size();i++){
        if(task_list[i].l<=max_location && task_list[i].r>=max_location){
            maximum_clique.push_back(task_list[i].idx);
        }
        else non_maximum_clique.push_back(task_list[i].idx);
    }
}

void coloring(){ // 탐욕적으로 구간 색상 지정, 증명 가능
    int i;
    sort(fall(task_list),col_comp);
    for(i=0;i<(int)maximum_clique.size();i++){
        task_color[task_list[i].idx]=i;
        color_last.push({task_list[i].r,i});
        color_count[i]=1;
        colors[i].insert(task_list[i].idx);
    }
    for(i=(int)maximum_clique.size();i<(int)task_list.size();i++){
        pair<int, int> tmp=color_last.top();
        color_last.pop();
        tmp.first=task_list[i].r;
        task_color[task_list[i].idx]=tmp.second;
        color_count[tmp.second]++;
        colors[tmp.second].insert(task_list[i].idx);
        color_last.push(tmp);
    }
    sort(fall(task_list),col_reset_comp);
}

void left_right_division(){ // 최대 클리크에 속하지 않은 것을 왼쪽과 오른쪽으로 분리해 저장
    int max_clique_start=0,max_clique_end=(int)1e9,i,j;
    for(i=0;i<(int)maximum_clique.size();i++){
        list_max.push_back(task_list[maximum_clique[i]]);
        if(task_list[maximum_clique[i]].l>max_clique_start){
            max_clique_start=task_list[maximum_clique[i]].l;
        }
        if(task_list[maximum_clique[i]].r<max_clique_end){
            max_clique_end=task_list[maximum_clique[i]].r;
        }
    }
    for(i=0;i<(int)non_maximum_clique.size();i++){
        if(task_list[non_maximum_clique[i]].r<max_clique_start){
            max_left.push_back(non_maximum_clique[i]);
            list_max_left.push_back(task_list[non_maximum_clique[i]]);
        }
        if(task_list[non_maximum_clique[i]].l>max_clique_end){
            max_right.push_back(non_maximum_clique[i]);
            list_max_right.push_back(task_list[non_maximum_clique[i]]);
        }
    }
}
void bipartite_matching(){ // 최대 클리크에 속한 것과 그렇지 않은 것 사이를 left_right_division 에서 저장한 것을 이용해 이분 매칭
    int i,j;
    sort(list_max_right.begin(),list_max_right.end(),align_left_normal);
    sort(list_max.begin(),list_max.end(),align_right_normal);
    bool chk[300000]={0};
        for(i=0,j=0; j<(int)list_max.size();j++){
            while(i<(int)list_max_right.size() && list_max_right[i].l<=list_max[j].r) i++;
            if(i>=(int)list_max_right.size()) break;
            bipartite_matches.emplace_back(list_max[j].idx,list_max_right[i].idx);
            chk[list_max[j].idx]=true;
            bipartite_match_idx[list_max_right[i].idx]=list_max[j].idx;
            bipartite_match_idx[list_max[j].idx]=list_max_right[i].idx;
        }
        sort(list_max.begin(),list_max.end(),align_left_normal);
        sort(list_max_left.begin(),list_max_left.end(),align_right_normal);
        for(i=0,j=0; j<(int)list_max.size();j++){
            while(i<(int)list_max_left.size() &&
                  (list_max_left[i].r>=list_max[j].l || chk[list_max[j].idx]==1)) i++;
            if(i>=(int)list_max_left.size()) break;
        bipartite_matches.emplace_back(list_max[j].idx,list_max_left[i].idx);
        bipartite_match_idx[list_max_left[i].idx]=list_max[j].idx;
        bipartite_match_idx[list_max[j].idx]=list_max_left[i].idx;
    }
}

void maximize_couples(){ // 크기 1인 독립집합 (즉 최대 클리크에 속한 것들) 중 이분 매칭에 따라 매칭 가능한 것 최대한 매칭
    vector<int> single;
    int i;
    for(i=0;i<(int)maximum_clique.size();i++){
        if(color_count[i]==1) single.push_back(i);
    }
    while(!single.empty()){
        int idx=*colors[single.back()].begin();
        single.pop_back();
        if(bipartite_match_idx[idx]!=-1){
            int id2=bipartite_match_idx[idx], id2_col=task_color[id2];
            bipartite_match_idx[idx]=bipartite_match_idx[id2]=-1;
            color_count[id2_col]--; color_count[task_color[idx]]++;
            colors[id2_col].erase(id2);
            colors[task_color[idx]].insert(id2);
            task_color[id2]=task_color[idx];
            if(color_count[id2_col]==1){
                single.push_back(id2_col);
            }
        }
    }
}

void left_right_bipartite(){ // 만약 모든 색에 대해 해당 색을 가진 구간이 "모두" 두 개 이상이거나 이하이면 굳이 이분 매칭을 하지 않아도 됨
    int i; bool x=0,y=0;
    for(i=0;i<(int)maximum_clique.size();i++){
        if(color_count[i]<2) x=1;
        if(color_count[i]>2) y=1;
    }
    if(x&&y){
        left_right_division();
        bipartite_matching();
        maximize_couples();
    }
}

void workers_matching(){ // 완성한 매칭에 따라 "학생" 부여
    int cnt=0,i,j;
    vector<int> single, even;
    vector<vector<int>> odd;
    for(i=0;i<(int)maximum_clique.size();i++){
        if(colors[i].size()%2==0){
            for(auto it : colors[i]) even.push_back(it);
            for(j=0;j<(int)even.size()-1;j+=2){
                workers[even[j]]=cnt;
                workers[even[j+1]]=cnt++;
            }
            even.clear();
        }
        elif(colors[i].size()%2==1 && colors[i].size()>1){
            odd.push_back({});
            for(int it : colors[i]) odd.back().push_back(it);
        }
    }
    for(i=0;i<(int)odd.size()-1;i+=2){
        if((int)odd.size()==1) break;
        int s1=odd[i].size()-1, s2=odd[i+1].size()-1;
        if(task_list[odd[i][s1-1]].l>task_list[odd[i][s1]].r) swap(odd[i][s1-1],odd[i][s1]);
        if(task_list[odd[i+1][s2-1]].l>task_list[odd[i+1][s2]].r) swap(odd[i+1][s2-1],odd[i+1][s2]);
        if(task_list[odd[i][s1-1]].r<task_list[odd[i+1][s2]].l){
            workers[odd[i][s1-1]]=cnt;
            workers[odd[i+1][s2]]=cnt++;
            odd[i][s1-1]=odd[i][s1];
        }
        else{
            workers[odd[i][s1]]=cnt;
            workers[odd[i+1][s2-1]]=cnt++;
            odd[i+1][s2-1]=odd[i+1][s2];
        }
        for(j=0;j<s1-1;j+=2){
            workers[odd[i][j]]=cnt;
            workers[odd[i][j+1]]=cnt++;
        }
        for(j=0;j<s2-1;j+=2){
            workers[odd[i+1][j]]=cnt;
            workers[odd[i+1][j+1]]=cnt++;
        }
    }
    if((int)odd.size()%2==1){
        for(i=0;i<(int)odd.back().size()-1;i+=2){
            workers[odd.back()[i]]=cnt;
            workers[odd.back()[i+1]]=cnt++;
        }
        workers[odd.back().back()]=cnt++;
    }
    for(i=0;i<(int)maximum_clique.size();i++){
        if(colors[i].size()==1){
            workers[*colors[i].begin()]=cnt++;
        }
    }
}

void output(){ // 이거 ㄹㅇ 어려움 진짜 어떻게 이런 함수를 짤 생각을 했냐
    int i;
    for(i=0;i<n;i++) {
        if(workers[i]<m) cout<<workers[i]+1<<" ";
        else cout<<0<<" ";
    }
}

signed main(){
    fast;
    init(); // O(n)
    find_maximum_clique(); // O(n log n)
    coloring(); // O(n log n)
    left_right_bipartite(); // O(n log n)
    workers_matching(); // O(n) probably
    output(); // O(n)
    return 0;
}
源文件, 语言: C++

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 28720kb

input:

7 5
9 10
7 9
3 4
9 10
2 6
8 9
5 8

output:

1 4 2 3 1 2 3

result:

ok answer = 7

Test #2:

score: 0
Accepted
time: 8ms
memory: 28780kb

input:

2 2
1 2
3 4

output:

1 1

result:

ok answer = 2

Test #3:

score: 0
Accepted
time: 10ms
memory: 28644kb

input:

2 1
1 2
2 3

output:

1 0

result:

ok answer = 1

Test #4:

score: 0
Accepted
time: 8ms
memory: 28712kb

input:

1 1
4 26

output:

1

result:

ok answer = 1

Test #5:

score: 0
Accepted
time: 2ms
memory: 28876kb

input:

500 258
1 3
3 5
2 4
3 5
4 5
4 5
1 4
1 2
3 5
2 5
2 5
4 5
4 5
4 5
2 3
1 4
1 4
1 4
4 5
4 5
2 3
4 5
3 5
3 5
1 5
1 4
2 5
1 5
3 5
3 4
4 5
2 3
3 5
3 5
4 5
2 3
1 5
1 5
2 3
2 3
3 4
3 5
3 4
1 3
1 2
1 5
4 5
2 3
2 4
1 3
4 5
4 5
4 5
1 3
3 5
4 5
3 5
1 5
1 2
1 2
3 5
3 5
4 5
3 4
3 5
2 3
2 5
2 4
2 5
3 5
2 3
1 5
4 5
...

output:

42 0 258 0 69 39 174 54 0 253 252 11 4 22 115 173 176 177 25 108 112 6 0 0 178 179 255 168 0 0 65 118 0 0 54 102 163 164 103 104 0 0 0 45 46 167 28 105 235 47 15 14 77 49 0 10 0 172 50 68 0 0 82 0 0 109 241 243 244 0 110 183 21 247 248 63 71 0 184 19 70 185 64 67 57 38 0 0 0 118 239 237 0 49 0 0 236...

result:

ok answer = 376

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 29160kb

input:

500 242
8 9
9 10
2 9
8 10
9 10
6 10
4 8
4 5
2 6
7 10
3 8
1 8
1 6
5 9
7 8
8 10
8 9
8 10
2 9
2 3
6 8
3 10
5 9
1 3
6 8
4 10
9 10
8 9
8 10
1 9
3 9
3 7
2 3
6 10
3 6
6 10
3 4
3 6
9 10
5 7
8 10
6 10
5 6
5 7
7 8
1 3
4 7
9 10
4 9
2 4
8 9
1 3
8 10
3 4
9 10
4 9
5 10
8 9
1 3
1 5
8 10
3 4
8 9
3 9
3 6
3 10
6 7
7 ...

output:

128 148 226 142 147 52 117 201 183 120 101 31 32 0 203 137 131 158 222 60 0 238 0 38 148 0 31 82 139 217 235 105 66 60 104 33 100 102 164 139 94 34 136 135 200 157 116 203 0 177 88 4 77 107 206 240 0 84 26 25 151 198 105 239 197 236 165 155 227 196 72 111 241 65 103 162 149 106 73 234 179 182 174 12...

result:

wrong answer participant answer = 452, judge answer = 471
English 繁體中文 简体中文

服务器时间: 2024-11-29 16:32:56 | 开源项目