글 읽기 - 이거 c#은 시간초과 못푸나요? c++이랑 똑같이 했는데...

powerlsj7 1년 전 1

C#이 느린 언어인건 아는데 파이썬보다는 빠르지 않나요? 파이썬도 통과하는데

//숏코딩에 c#풀이가 하나도 없는게 ㅡ;ㅡ;;

아니면 c#으로 풀려면 다른 방법이 존재하는 건가요?;;

ㅠㅠ

#include<iostream>
#include<vector>
typedef long long ll;
using namespace std;
ll node[100000 * 4];
vector<int> answer;
void SegmentTreeUpdate(ll s, ll e, ll num, ll parent)
{
    if (s > num || e < num)
    {
        return;
    }
    if (s == e)
    {
        node[parent]++;
        return;
    }
    ll mid = (s + e) / 2;
    ll left = parent * 2 + 1;
    ll right = parent * 2 + 2;
    SegmentTreeUpdate(s, mid, num, left);
    SegmentTreeUpdate(mid + 1, e, num, right);
    node[parent] = node[left] + node[right];
}
void SegmentTreeDelete(ll s, ll e, ll num, ll parent)
{
    node[parent]--;
    if (s == e)
    {
        answer.push_back(s);
        return;
    }
    ll mid = (s + e) / 2;
    ll left = parent * 2 + 1;
    ll right = parent * 2 + 2;
    if (node[left] >= num)
    {
        SegmentTreeDelete(s, mid, num, left);
    }
    else
    {
        SegmentTreeDelete(mid + 1, e, num-node[left], right);
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        SegmentTreeUpdate(0, 100000, i, 0);
    }
    int idx = k;
    int size = n;
    cout << "<";
    for (int i = 0; i < size; i++)
    {
        SegmentTreeDelete(0, 100000, idx, 0);
        idx =idx+k-1;
        n -= 1;
        while (n!=0&&idx > n)
        {
            idx -= n;
        }
    }
    for (int i = 0; i < (int)answer.size(); i++)
    {
        cout << answer[i];
        if (i == (int)answer.size()-1)
        {
            continue;
        }
        cout << ", ";
    }
    cout << ">";
    return 0;
}



//////////////////////밑에는 c# 똑같습니다.



using System;
using System.IO;
using System.Text;
using System.Collections.Generic;
class Program
{
    static StreamReader sr = new StreamReader(Console.OpenStandardInput(), Encoding.Default);
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput(), Encoding.Default);
    static int[] node = new int[100000 * 4];
    static List<int> answer = new List<int>();
    static void SegmentTreeUpdate(int s, int e, int num, int parent)
    {
        if (s > num || e < num)
        {
            return;
        }
        if (s.Equals(e))
        {
            node[parent]++;
            return;
        }
        int mid = (s + e) / 2;
        int left = parent * 2 + 1;
        int right = parent * 2 + 2;
        SegmentTreeUpdate(s, mid, num, left);
        SegmentTreeUpdate(mid + 1, e, num, right);
        node[parent] = node[left] + node[right];
    }
   static  void SegmentTreeDelete(int s, int e, int num, int parent)
    {
        node[parent]--;
        if (s.Equals(e))
        {
            node[parent]--;
            answer.Add(s);
            return;
        }
        int mid = (s + e) / 2;
        int left = parent * 2 + 1;
        int right = parent * 2 + 2;
        if (num <= node[left])
        {
            SegmentTreeDelete(s, mid, num, left);
        }
        else
        {
            SegmentTreeDelete(mid + 1, e, num - node[left], right);
        }
    }
    static void Main(string[] args)
    {
        int n, k;
        string[] str = sr.ReadLine().Split();
        n = int.Parse(str[0]);
        k = int.Parse(str[1]);
        for (int i = 1; i <= n; i++)
        {
            SegmentTreeUpdate(0, 100000, i, 0);
        }
        int idx = k;
        int size = n;
        for (int i = 0; i < n; i++)
        {
            SegmentTreeDelete(0, 100000, idx, 0);
            idx = idx + k - 1;
            size--;
            while (!size.Equals( 0)&&idx > size)
            {
                idx -= size;
            }
        }
        sw.Write("<");
        for (int i = 0; i < n; i++)
        {
            sw.Write(answer[i]);
            if (i.Equals(n - 1))
            {
                continue;
            }
            sw.Write(", ");
        }
        sw.Write(">");
        sw.Close();
    }
}



///////////////////////C#이 느린 언어인건 아는데 파이썬보다는 빠르지 않나요? 파이썬도 통과하는데 
//숏코딩에 c#풀이가 하나도 없는게 ㅡ;ㅡ;;

lcr7324 1년 전 1

백준의 문제는 반드시 모든 언어로 풀리는 것을 보장하지 않습니다. 그래야 할 이유도 사실 없고요. (오히려, 언어별 시간 및 메모리 보너스를 제공하는 채점 사이트는 백준을 제외하면 거의 없는 것으로 압니다.)

이 문제는 특히 "추가 시간 없음"을 명시했기에 기존 C# 코드에 주어지는 x2 + 1초의 보너스(https://help.acmicpc.net/langu...)도 없고, 파이썬처럼 문제 하단에서 따로 시간 제한을 늘려주지도 않았으니 반드시 0.15초 이내에 동작해야 합니다. 쉽지는 않겠군요.

애초에 C#이 PS에서 잘 안 쓰이는 언어 중 하나이기 때문에, 어쩔 수 없는 부분이 아닐까 싶습니다.

문제

문제

출처

ICPC

이거 c#은 시간초과 못푸나요? c++이랑 똑같이 했는데...

powerlsj7 1년 전 1

lcr7324 1년 전 1

powerlsj7 1년 전 0

bacon8282 7달 전 1

powerlsj7 7달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말