Submission #1010961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010961		isaachew	Card Collection (JOI24_collection)	C++17	0 / 100	0 ms	344 KiB

Main

#include <bits/stdc++.h>
/*
 To get a certain card value, min/max operations must be done to the cost
 Only dependent on lower/equal/greater than correct value
 In the end, cost and value must be combined in the same part
 
 (1 1) iff both have max 1
 (-1 -1) iff both have max -1
 Do not create (-1 1) - cannot do anything about it after (0 0)
 
 (1 0) and (0 -1) - must have a (1 -1) or (-1 1) (anywhere)
 
 (1 0) needs (-1 1), (0 -1) needs (1 -1)
Then min/max
 If >3 (1 -1)s, always possible
 
 If (0 0), left/right cannot all be (1 -1) or (-1 1)
 If (1 0) (0 -1) (both decreasing), there must be dec in middle/left, or inc in middle/right (cannot be)
 
 If (1 0) (0 1),
 
 ----+- -> - only
 2 + -> can do +
 -----+ -> can do +
 
 Can do + if end in + or at least 2 +
 
 If middle has both - and +, def possible
 
 
 Through max/min, differences always decrease
 
 They can both be - and + and doesn't matter, or -++++++-
 */
int main(){
    int n,q;
    std::cin>>n>>q;
    std::vector<std::pair<int,int>> nums;
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        nums.push_back({a,b});
    }
    std::vector<int> result;
    for(int i=0;i<q;i++){
        int a,b;
        std::cin>>a>>b;
        std::vector<int> nnums;
        std::vector<int> nprefs,nsuffs(n);
        std::set<int> nminus,nplus;
        std::vector<int> nwzp,nwzn,nwz;
        int neuleft=3;//3 for neu only, -2 for neg, -1 for neg/neu, 0 for all
        for(int j=0;j<n;j++){
            if(nums[j].first<a&&nums[j].second>b){
                if(j==0)neuleft=2;
                else neuleft=std::min(0,neuleft+1);
                nnums.push_back(1);
                nplus.insert(j);
            }
            if(nums[j].first<a&&nums[j].second==b||nums[j].first==a&&nums[j].second>b){
                nnums.push_back(2);
                neuleft=std::min(0,neuleft+1);
                nplus.insert(j);
                nwzp.push_back(j);
            }
            if(nums[j].first<a&&nums[j].second<b||nums[j].first>a&&nums[j].second>b){
                if(neuleft==-2)neuleft=-1;
                if(neuleft==2)neuleft=1;
                nnums.push_back(0);
            }
            
            if(nums[j].first>a&&nums[j].second==b||nums[j].first==a&&nums[j].second<b){
                nnums.push_back(-2);
                neuleft=std::max(0,neuleft-1);
                nminus.insert(j);
                nwzn.push_back(j);
            }
            if(nums[j].first>a&&nums[j].second<b){
                if(j==0)neuleft=-2;
                else neuleft=std::max(0,neuleft-1);
                nnums.push_back(-1);
                nminus.insert(j);
            }
            if(nums[j].first==a&&nums[j].second==b){
                nnums.push_back(0);
                nwz.push_back(j);
            }
            nprefs.push_back(neuleft);
        }
        int neuright=3;
        for(int j=n;j--;){
            if(nnums[j]==1){
                if(j==0)neuright=2;
                else neuright=std::min(0,neuright+1);
            }
            if(nnums[j]==2)neuright=std::min(0,neuright+1);
            if(nnums[j]==0){
                if(neuright==-2)neuright=-1;
                if(neuright==2)neuright=1;
            }
            if(nnums[j]==-1){
                if(j==0)neuright=-2;
                else neuright=std::max(0,neuright-1);
            }
            if(nnums[j]==-2)neuright=std::max(0,neuright-1);
            nsuffs[j]=neuright;
        }
        bool can=false;
        if(!nwzp.empty()&&!nwzn.empty()){
            auto lnb=nminus.upper_bound(nwzp[0]);
            auto lpb=nplus.lower_bound(nwzn.back());
            if(lpb!=nplus.begin()&&lnb!=nminus.end()){
                can=true;
            }
            lnb=nminus.upper_bound(nwzn[0]);
            lpb=nplus.lower_bound(nwzp.back());
            if(lpb!=nplus.begin()&&lnb!=nminus.end()){
                can=true;
            }
        }
        if(!nwz.empty()){
            int pr1=nprefs[nwz[0]];
            int pr2=nsuffs[nwz[0]];
            if(pr1!=2&&pr1!=-2&&pr2!=2&&pr2!=-2){
                can=true;
            }
        }
        if(!can){
            int cni=0;
            for(int j=0;j<nwzp.size();j++){
                while(cni<nwzn.size()&&nwzn[cni]<nwzp[j])cni++;
                if(cni>=nwzn.size())break;
                if(nprefs[nwzp[j]]*nsuffs[nwzn[cni]]<=0){
                    can=true;
                    break;
                }
            }
            cni=0;
            for(int j=0;j<nwzn.size();j++){
                
                while(cni<nwzp.size()&&nwzp[cni]<nwzn[j])cni++;
                if(cni>=nwzp.size())break;
                if(nprefs[nwzn[j]]*nsuffs[nwzp[cni]]<=0){
                    can=true;
                    break;
                }
            }
        }
        if(can)result.push_back(i);
    }
    for(int i:result)std::cout<<i+1<<' ';
    std::cout<<'\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:60:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |             if(nums[j].first<a&&nums[j].second==b||nums[j].first==a&&nums[j].second>b){
Main.cpp:66:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |             if(nums[j].first<a&&nums[j].second<b||nums[j].first>a&&nums[j].second>b){
Main.cpp:72:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   72 |             if(nums[j].first>a&&nums[j].second==b||nums[j].first==a&&nums[j].second<b){
Main.cpp:130:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             for(int j=0;j<nwzp.size();j++){
      |                         ~^~~~~~~~~~~~
Main.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |                 while(cni<nwzn.size()&&nwzn[cni]<nwzp[j])cni++;
      |                       ~~~^~~~~~~~~~~~
Main.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |                 if(cni>=nwzn.size())break;
      |                    ~~~^~~~~~~~~~~~~
Main.cpp:139:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for(int j=0;j<nwzn.size();j++){
      |                         ~^~~~~~~~~~~~
Main.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                 while(cni<nwzp.size()&&nwzp[cni]<nwzn[j])cni++;
      |                       ~~~^~~~~~~~~~~~
Main.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |                 if(cni>=nwzp.size())break;
      |                    ~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 38
• Subtask 3: 0 / 22
• Subtask 4: 0 / 29