Submission #524607


Source Code Expand

Copy
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <cmath>

using namespace std;

struct vertex{
    int X;
    int Y;
};

int	gcd(int	a, int b){
    while( b ){
        int	m = a % b;
        a = b;
        b = m;
    }
    return a;
}

int	lcm(int a, int	b){
    return (a*b)/gcd(a,b);
}

int isPrim(int a){
    if(a==1){
        return 0;
    }
    for(int i=2;i<=(a+1)/2;i++){
        if(a%i==0){
            return 0;
        }
    }
    return 1;
}

int main(int argc, const char * argv[])
{
    //std::ios::sync_with_stdio(false);
    //scanf("%s",S);
    //scanf("%d",&N);
    //getline(cin, target);
    //cin >> x >> y;
    //ここから

    int N,M;
    cin >> N >> M;
    int s[100000];
    int t[100000];
    
    for(int i=0;i<M;i++){
        cin >> s[i];
        cin >> t[i];
    }
    
    int zou[300000];
    int kasan[300000];
    
    vector<int>zero;
    zero.clear();
    for(int i=0;i<300000;i++){
        zou[i]=0;
    }
    for(int i=0;i<M;i++){
        zou[s[i]]++;
        zou[t[i]+1]--;
    }
    for(int i=1;i<=N;i++){
        if(i==1){
            kasan[i]=zou[i];
        }else{
            kasan[i]=kasan[i-1]+zou[i];
        }
        if(kasan[i]==1){
            zero.push_back(i);
        }
    }
    vector<int>ans;
    ans.clear();
    int anscnt=0;
    for(int i=0;i<M;i++){
        int flag=0;
        for(int j=0;j<zero.size();j++){
            if(s[i]<=zero[j] && zero[j]<=t[i]){
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans.push_back(i+1);
            anscnt++;
        }
    }
    
    cout << anscnt << endl;
    for(int i=0;i<ans.size();i++){
        cout << ans[i]<< endl;

    }
    //cout << endl;
    
    //ここまで
    //cout << "ans" << endl;改行含む
    //printf("%.0f\n",ans);//小数点以下表示なし
    //printf("%.7f",p);
    //printf("%f\n",pow(2,ans.size()));
    
    return 0;
}

Submission Info

Submission Time
Task B - ドキドキデート大作戦高橋君
User ikeha
Language C++ (GCC 4.9.2)
Score 0
Code Size 2178 Byte
Status
Exec Time 2041 ms
Memory 6076 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 0 / 30 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All 0 / 70 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt 40 ms 2176 KB
subtask0_sample_02.txt 34 ms 2140 KB
subtask0_sample_03.txt 34 ms 2136 KB
subtask1_01.txt 2041 ms 6076 KB
subtask1_02.txt 380 ms 4680 KB
subtask1_03.txt 2040 ms 4276 KB
subtask1_04.txt 2038 ms 4112 KB
subtask1_05.txt 2040 ms 4088 KB
subtask1_06.txt 38 ms 2128 KB
subtask1_07.txt 35 ms 2124 KB
subtask1_08.txt 35 ms 2120 KB
subtask1_09.txt 35 ms 2120 KB
subtask2_01.txt 343 ms 4764 KB
subtask2_02.txt 363 ms 4760 KB
subtask2_03.txt 36 ms 2112 KB
subtask2_04.txt 35 ms 2120 KB
subtask2_05.txt 34 ms 2144 KB
subtask2_06.txt 34 ms 2144 KB
subtask2_07.txt 32 ms 2124 KB
subtask2_08.txt 413 ms 4420 KB