QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812057#9156. 百万富翁dvbs2000Compile Error//C++144.8kb2024-12-13 11:08:302024-12-13 11:08:32

Judging History

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

  • [2024-12-13 11:08:32]
  • 评测
  • [2024-12-13 11:08:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// 读写优化
inline int read() {
    static char buf[1<<20], *p1=buf, *p2=buf;
    if(p1==p2) {
        p2=(p1=buf)+fread(buf,1,1<<20,stdin);
        if(p1==p2) return EOF;
    }
    return *p1++;
}
inline int rd() {
    int x=0;char c;
    do c=(char)read();while(c<'0' || c>'9');
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c&15), c=(char)read();
    return x;
}

const int INF = 1000000000;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,q;
    cin >> n >> m >> q;

    // A[i]与B[i]的输入
    vector<array<int,3>> A(n), B(n);
    for (int i=0; i<n; i++){
        cin >> A[i][0] >> A[i][1] >> A[i][2];
    }
    for (int i=0; i<n; i++){
        cin >> B[i][0] >> B[i][1] >> B[i][2];
    }

    // 排序每个三元组,检查是否相等集
    vector<int> same(n,1);
    for (int i=0; i<n; i++){
        sort(A[i].begin(), A[i].end());
        sort(B[i].begin(), B[i].end());
        for (int j=0; j<3; j++){
            if (A[i][j]!=B[i][j]) {same[i]=0;break;}
        }
    }

    // 构建映射信息
    // 我们需要记录每个 A元素 在哪些位置出现,以及它映射到的 B元素
    // 同时记录每个 B元素 在哪些位置出现,以及它是由哪个 A元素映射来的
    // 由于m可以很大,用vector<vector<pair<int,int>>>来存储
    // domain_map[a]存储(位置pos, 映射到的b)
    // codomain_map[b]存储(位置pos, 来自的a)
    // 注意:只有 same[i]=1 的位置才需要记录映射,因为 same=0 的位置无效(该区间必然不匹配)
    vector<vector<pair<int,int>>> domain_map(m+1), codomain_map(m+1);

    for (int i=0; i<n; i++){
        if (same[i]==1) {
            // p(A[i][j]) = B[i][j]
            for (int j=0; j<3; j++){
                int a = A[i][j];
                int b = B[i][j];
                domain_map[a].push_back({i+1,b});
                codomain_map[b].push_back({i+1,a});
            }
        }
    }

    // 产生冲突对
    // 对 domain_map 中每个元素的出现列表,若相邻出现映射的b不同,则形成冲突对
    // 对 codomain_map 同理
    vector<pair<int,int>> conflicts; // (x,y) with x<y

    auto check_conflicts = [&](vector<vector<pair<int,int>>> &mp, bool domain_side){
        for (int x=1; x<=m; x++){
            auto &occ = mp[x];
            if (occ.empty()) continue;
            // occ已按照位置存储吗?
            // 我们插入是 (pos, val) 按照i顺序自然是有序的,因为 i 是顺序递增插入的
            // 同一元素在同一位置只出现一次,所以天然按pos有序
            // 若不放心,可以对 occ 按 pos 排序
            // 但按构造 pos 是 i+1 递增加入的,原本就有序。
            // 如保险起见: 
            // sort(occ.begin(), occ.end());
            
            for (int k=0; k+1<(int)occ.size(); k++){
                int pos1 = occ[k].first;
                int pos2 = occ[k+1].first;
                int val1 = occ[k].second;
                int val2 = occ[k+1].second;
                if (val1 != val2) { 
                    // 冲突 (pos1,pos2)
                    // 任意包含这两个位置的区间无法构成有效映射
                    // 确保 pos1<pos2
                    if (pos1<pos2) conflicts.push_back({pos1,pos2});
                    else conflicts.push_back({pos2,pos1});
                }
            }
        }
    };

    check_conflicts(domain_map,true);
    check_conflicts(codomain_map,false);

    // 根据冲突对构建 conflictLeft 与 conflictPrefix
    // conflictLeft[j]: 以 j 为右端点的冲突对中最小的左端点
    // 初始化为INF
    vector<int> conflictLeft(n+1, INF);

    for (auto &cf: conflicts){
        int x=cf.first,y=cf.second;
        // y 位置的冲突起点至少是 x
        if (y<=n) conflictLeft[y]=min(conflictLeft[y], x);
    }

    vector<int> conflictPrefix(n+1, INF);
    // 前缀最小值
    for (int i=1; i<=n; i++){
        conflictPrefix[i]=min(conflictPrefix[i-1], conflictLeft[i]);
    }

    // samePrefix: 统计 same[i]==0 的数量前缀和
    vector<int> zeroPrefix(n+1,0);
    for (int i=1; i<=n; i++){
        zeroPrefix[i] = zeroPrefix[i-1] + (1 - same[i-1]); 
    }

    // 查询
    // 条件:
    // 1. zeroPrefix[r]-zeroPrefix[l-1]>0 => No
    // 2. conflictPrefix[r]>=l => No
    // else Yes

    while (q--){
        int l,r;cin>>l>>r;
        if (zeroPrefix[r]-zeroPrefix[l-1]>0) {
            cout<<"No\n";
        } else {
            if (conflictPrefix[r]>=l) {
                cout<<"No\n";
            } else {
                cout<<"Yes\n";
            }
        }
    }

    return 0;
}

Details

/usr/bin/ld: /tmp/cctm4PYQ.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccRRiZ1Q.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccRRiZ1Q.o: in function `main':
implementer.cpp:(.text.startup+0x1df): undefined reference to `richest(int, int, int)'
collect2: error: ld returned 1 exit status